Pemahaman mendalam tentang algoritma isihan sisipan dan prinsip pelaksanaannya dalam Java

Pemahaman mendalam tentang algoritma isihan sisipan dan prinsip pelaksanaannya dalam Java

Isihan sisipan ialah algoritma isihan yang mudah tetapi biasa digunakan, dan prinsip pelaksanaannya juga agak mudah. Artikel ini akan menyelidiki algoritma isihan sisipan dan prinsip pelaksanaannya dalam Java, dan melampirkan contoh kod tertentu.

1. Idea algoritma isihan sisipan
Idea isihan sisipan adalah untuk memasukkan elemen untuk diisih ke dalam kedudukan yang sesuai dalam urutan separa yang telah tersusun, dengan itu membahagikan jujukan kepada bahagian yang diisih dan tidak diisih. Semasa proses penyisihan, dengan sentiasa membandingkan dan mengalihkan kedudukan unsur, urutan tersusun sepenuhnya akhirnya diperolehi.

2. Langkah khusus algoritma isihan sisipan
Langkah khusus algoritma isihan sisipan boleh dibahagikan kepada langkah berikut:

1. Mulakan dari elemen pertama dan anggap ia sebagai urutan yang diisih.
2. Keluarkan elemen seterusnya, rentas dari belakang ke hadapan dalam urutan yang diisih, dan cari kedudukan sisipan yang sesuai.
3. Masukkan elemen ke dalam kedudukan yang sesuai dalam urutan yang disusun.
4. Ulang langkah 2 dan langkah 3 sehingga semua elemen dimasukkan ke dalam kedudukan yang sepatutnya.

3. Kod pelaksanaan algoritma isihan sisipan
Berikut ialah contoh kod pelaksanaan algoritma isihan sisipan dalam Java:

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; 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;
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 1, 3, 8, 4, 7, 2, 6};
        insertionSort(arr);
        System.out.println("排序结果：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Dalam kod di atas, insertionSort方法使用插入排序算法对数组进行排序。在每一次遍历中，将当前元素存储为key，然后将key与已排序序列中的元素逐个比较并移动位置，直到找到合适的插入位置。最后，将key dimasukkan ke dalam kedudukan yang betul.

4. Kerumitan masa dan kerumitan ruang isihan sisipan
Kerumitan masa isihan sisipan ialah O(n^2), dengan n ialah panjang jujukan yang hendak diisih. Dalam kes yang paling teruk, di mana urutan adalah dalam susunan terbalik, n(n-1)/2 operasi perbandingan dan pergerakan diperlukan. Tetapi dalam keadaan biasa, isihan sisipan berfungsi dengan baik.

Kerumitan ruang isihan sisipan ialah O(1) kerana ia hanya memerlukan tahap ruang tambahan yang tetap untuk menyimpan pembolehubah sementara. Isih. Prinsip pelaksanaannya agak mudah dan sesuai untuk pengisihan data berskala kecil. Pemahaman dan amalan isihan sisipan yang mendalam dapat membantu kami memahami konsep teras algoritma dan struktur data dengan lebih baik.

Di atas ialah pemahaman yang mendalam tentang algoritma isihan sisipan dan prinsip pelaksanaannya dalam Java dan pengenalan kepada contoh kod tertentu. Harap ini membantu!

Atas ialah kandungan terperinci Pemahaman mendalam tentang algoritma isihan sisipan dan prinsip pelaksanaannya dalam Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!