Memahami Algoritma Isih Sisipan (dengan Contoh dalam Java)

Isihan sisipan ialah algoritma isihan berulang. Ia membina subarray yang diisih satu elemen pada satu masa dengan memasukkan setiap elemen yang tidak diisih ke dalam kedudukan yang betul dalam subarray yang diisih. Fikirkan untuk mengisih tangan bermain kad – anda mulakan dengan satu kad yang diisih, kemudian masukkan setiap kad berikutnya ke tempat yang sepatutnya di antara kad yang telah diisih.

Cara Isih Sisipan Berfungsi

Mari kita gambarkan dengan tatasusunan contoh yang ingin kita susun dalam tertib menaik:

Lelaran Pertama:

Kami menganggap elemen pertama sudah diisih. Algoritma bermula dengan elemen kedua.

Membandingkan 2 dengan 8, sejak 2 < 8, kita alihkan 8 ke kanan dan masukkan 2 ke kiri.

Lelaran Kedua:

Kami membandingkan 6 dengan subarray yang diisih (2, 8). 6 < 8, jadi 8 anjakan ke kanan. Kemudian, sejak 6 > 2, 6 diletakkan di sebelah kanan 2.

Proses ini berterusan sehingga keseluruhan tatasusunan diisih.

Pelaksanaan dalam Java

import java.util.Arrays;

public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

Kod berulang, mengambil setiap elemen sebagai key. Ia kemudian membandingkan key dengan elemen dalam bahagian yang diisih, mengalihkan elemen yang lebih besar ke kanan sehingga kedudukan yang betul untuk key ditemui.

Sebagai contoh, dalam lelaran kedua (i=2):

key ialah 6. Gelung while menganjak elemen sehingga kedudukan yang betul ditemui:

Akhir sekali, 6 dimasukkan:

Output:

Tatasusunan tidak diisih: [8, 2, 6, 4, 9, 1] Tatasusunan diisih: [1, 2, 4, 6, 8, 9]

Analisis Kerumitan

• Kerumitan Masa:
  • Kes Terbaik (O(n)): Tatasusunan sudah diisih.
  • Kes Purata (O(n²)): Elemen yang disusun secara rawak.
  • Kes Terburuk (O(n²)): Tatasusunan diisih terbalik.
• Kerumitan Angkasa: O(1) (Algoritma di tempat)

Kesimpulan

Kerumitan masa kuadratik jenis sisipan menjadikannya tidak cekap untuk set data yang besar. Walau bagaimanapun, ia adalah algoritma yang mudah dan berfungsi dengan baik pada set data kecil atau data yang hampir diisih.

Atas ialah kandungan terperinci Memahami Algoritma Isih Sisipan (dengan Contoh dalam Java). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!