Penjelasan terperinci tentang algoritma isihan sisipan yang dilaksanakan di Jawa

Penjelasan terperinci kaedah pelaksanaan algoritma isihan sisipan Java

Isihan sisipan ialah algoritma isihan yang mudah dan intuitif Prinsipnya ialah membahagikan urutan yang akan diisih kepada bahagian yang diisih dan tidak diisih, dan setiap kali ia tidak diisih. Ambil elemen dan masukkan ke dalam kedudukan disusun yang sesuai. Kaedah pelaksanaan algoritma isihan sisipan adalah agak mudah Kaedah pelaksanaan khusus akan diperkenalkan secara terperinci di bawah dan contoh kod yang sepadan akan diberikan.

1. Idea algoritma
   Andaikan anda ingin mengisih tatasusunan integer dalam tertib menaik Pada mulanya, arr[0] dianggap sebagai bahagian yang diisih, dan elemen yang selebihnya dianggap sebagai bahagian yang tidak diisih. Berdasarkan ini, jika elemen semasa yang hendak dimasukkan ialah arr[i] (i bermula dari 1), maka cari kedudukan j di mana arr[i] harus disisipkan daripada bahagian yang disusun arr[0:i-1], dan kemudian arr[i] dimasukkan ke dalam kedudukan j, dan semua elemen arr[j:i-1] digerakkan ke belakang satu kedudukan dalam urutan.
2. Pelaksanaan kod
   Berikut ialah contoh kod untuk melaksanakan 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;

            // 将已排序的元素依次向后移动，直到找到arr[i]应该插入的位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1};
        insertionSort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. Analisis algoritma
   Kerumitan masa algoritma isihan sisipan ialah O(n^2), dengan n ialah nombor unsur yang hendak diisih . Dalam kes terbaik, iaitu tatasusunan yang hendak diisih sudah diisih, kerumitan masa isihan sisipan ialah O(n). Dalam kes yang paling teruk, tatasusunan yang hendak diisih adalah dalam susunan terbalik, dan kerumitan masa isihan sisipan ialah O(n^2). Isih sisipan ialah algoritma pengisihan yang stabil kerana kedudukan relatif unsur yang sama tidak berubah sebelum dan selepas pengisihan.

Ringkasnya, artikel ini memperkenalkan kaedah pelaksanaan algoritma isihan sisipan Java secara terperinci dan memberikan contoh kod yang sepadan. Isih sisipan ialah algoritma pengisihan yang mudah dan intuitif sesuai untuk tatasusunan berskala kecil atau tatasusunan tersusun pada dasarnya. Dalam aplikasi praktikal, isihan sisipan boleh digantikan dengan algoritma pengisihan lain yang lebih cekap, tetapi memahami prinsip dan kaedah pelaksanaan isihan sisipan adalah sangat berfaedah untuk mempelajari algoritma pengisihan lain.

Atas ialah kandungan terperinci Penjelasan terperinci tentang algoritma isihan sisipan yang dilaksanakan di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!