Kaedah dan prinsip menulis algoritma isihan sisipan dalam Java

Langkah dan idea algoritma isihan sisipan

Isihan sisipan ialah algoritma isihan yang mudah dan intuitif ialah memasukkan unsur-unsur yang hendak diisih ke dalam kedudukan yang sesuai bagi urutan yang diisih.

Langkah khusus adalah seperti berikut:

1. Mula-mula, kami membahagikan tatasusunan kepada dua bahagian: bahagian yang diisih dan bahagian yang tidak diisih. Pada mulanya, terdapat hanya satu elemen dalam bahagian yang diisih, iaitu elemen pertama tatasusunan.
2. Kami mengeluarkan elemen dari bahagian yang belum diisi secara bergilir-gilir, membandingkannya dengan elemen dalam bahagian yang disusun satu demi satu, dan mencari kedudukan yang sesuai untuk dimasukkan.
3. Semasa proses perbandingan, kami mengalihkan elemen dalam bahagian yang diisih ke belakang untuk memberi ruang kepada elemen yang dimasukkan.
4. Akhir sekali, kami memasukkan semua elemen dalam bahagian yang tidak diisih ke dalam kedudukan yang sesuai bagi bahagian yang diisih, dan pengisihan selesai.

Berikut ialah contoh kod untuk menulis algoritma isihan sisipan dalam bahasa 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 = {5, 2, 8, 1, 9, 3};
        System.out.println("原数组：");
        printArray(arr);
        insertionSort(arr);
        System.out.println("排序后的数组：");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Dalam contoh kod ini, kami mentakrifkan kaedah insertionSort yang menerima tatasusunan integer sebagai parameter dan melaksanakan fungsi pada tatasusunan Lakukan isihan sisipan. Kami menggunakan n untuk mewakili panjang tatasusunan dan menggunakan for untuk melingkari elemen bahagian yang tidak diisih. Dalam setiap traversal, kami menyimpan elemen semasa arr[i] ke dalam pembolehubah key, dan kemudian melintasi bahagian yang diisih ke hadapan untuk mencari kedudukan yang sesuai untuk memasukkan kunci . Semasa proses perbandingan, kami mengalihkan elemen yang lebih besar ke belakang satu kedudukan untuk memberi ruang kepada kunci. Akhir sekali, kami memasukkan key ke dalam kedudukan yang betul dan pengisihan selesai. insertionSort方法，它接受一个整数数组作为参数，并对数组进行插入排序。我们用n表示数组的长度，并使用for循环遍历未排序部分的元素。在每一次遍历中，我们将当前元素arr[i]保存到key变量中，然后向前遍历已排序部分，找到合适的位置插入key。在比较的过程中，我们将较大的元素往后移动一位，为key腾出位置。最后，我们将key插入到正确的位置上，排序完成。

在main方法中，我们初始化一个整数数组arr，并调用insertionSort方法对数组进行排序。最后，我们调用printArray

Dalam kaedah utama, kami memulakan tatasusunan integer arr dan memanggil kaedah insertionSort untuk mengisih tatasusunan. Akhir sekali, kami memanggil kaedah printArray untuk mencetak tatasusunan yang diisih.

Dengan menjalankan kod di atas, anda boleh mendapatkan output berikut:

原数组：
5 2 8 1 9 3 
排序后的数组：
1 2 3 5 8 9 

Kerumitan masa bagi algoritma isihan sisipan ialah O(n^2), dengan n ialah panjang tatasusunan. Walaupun algoritma isihan sisipan mempunyai kerumitan masa yang tinggi, pelaksanaannya adalah mudah dan sesuai untuk pengisihan tatasusunan berskala kecil. Pada masa yang sama, dalam aplikasi praktikal, algoritma isihan sisipan juga mempunyai ciri-ciri kestabilan. 🎜

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