Isih Sisipan dalam Java

Jika anda seorang pengaturcara, anda mesti pernah mendengar tentang menyusun banyak. Isih pada asasnya menyusun unsur-unsur sama ada dalam tertib menaik atau dalam tertib menurun. Terdapat begitu banyak algoritma pengisihan yang tersedia untuk mengisih elemen, dan setiap algoritma mempunyai cara yang berbeza untuk mengisih, kerumitan yang berbeza. Jadi ia bergantung pada senario tertentu dan bilangan elemen tentang algoritma yang harus digunakan. Sisipan juga merupakan salah satu algoritma pengisihan yang biasa digunakan dengan kerumitan O(n^2) dan dilakukan seperti kita mengisih kad permainan di tangan kita. Dalam topik ini, kita akan belajar tentang Isih Sisipan dalam Java.

Mulakan Kursus Pembangunan Perisian Percuma Anda

Pembangunan web, bahasa pengaturcaraan, ujian perisian & lain-lain

Bagaimana Isih Sisipan Berfungsi dalam Java?

Mari kita fahami cara kerja Isihan Sisipan menggunakan contoh.

Andaikan terdapat tatasusunan dengan nama arr yang mempunyai elemen yang disebut di bawah:

10 5 8 20 30 2 9 7

Langkah #1 – Isih sisipan bermula dengan elemen ke-2 tatasusunan, iaitu 5, dengan mengambil kira elemen pertama tatasusunan yang pelbagai dalam dirinya sendiri. Kini elemen 5 dibandingkan dengan 10 kerana 5 adalah kurang daripada 10, jadi 10 dialihkan 1 kedudukan ke hadapan dan 5 dimasukkan sebelum itu.

Kini tatasusunan yang terhasil ialah:

5 10 8 20 30 2 9 7

Langkah #2 – Kini elemen arr[2], iaitu 8 dibandingkan dengan elemen arr[1], iaitu 10. Oleh kerana 8 lebih kecil daripada elemen sebelumnya 10, ia dianjakkan satu melangkah ke hadapan dari kedudukannya, dan kemudian ia dibandingkan dengan 5. Memandangkan 8 lebih besar daripada 5, jadi ia dimasukkan selepasnya.

Maka tatasusunan yang terhasil ialah :

5 8 10 20 30 2 9 7

Langkah #3 – Kini elemen 20 dibandingkan dengan 10 kerana ia lebih besar daripada 10, ia kekal pada kedudukannya.

5 8 10 20 30 2 9 7

Langkah #4 – Elemen 30 dibandingkan dengan 20, dan memandangkan ia lebih besar daripada 20, tiada perubahan akan dibuat dan tatasusunan kekal seperti sedia ada. Sekarang tatasusunan akan menjadi

5 8 10 20 30 2 9 7

Langkah #5 – Elemen 2 dibandingkan dengan 30, kerana ia lebih kecil daripada 30, ia dianjak satu kedudukan ke hadapan kemudian ia dibandingkan dengan 20,10, 8, 5, satu demi satu dan semua elemen dialihkan kepada 1 kedudukan di hadapan, dan 2 dimasukkan sebelum 5.

Tatasusunan yang terhasil ialah:

2 5 8 10 20 30 9 7

Langkah #6 – Elemen 9 dibandingkan dengan 30 kerana ia lebih kecil daripada 30; ia dibandingkan dengan 20, 10 satu demi satu, dan elemen akan dianjakkan 1 kedudukan ke hadapan, dan 9 dimasukkan sebelum 10 dan selepas 8.

Tatasusunan yang terhasil ialah:

2 5 8 9 10 20 30 7

Langkah #7 – Elemen 7 dibandingkan dengan 30, dan memandangkan ia lebih kecil daripada 30, ia dibandingkan dengan 30, 20, 10, 9, 8 dan semua elemen dianjakkan 1 kedudukan di hadapan satu demi satu, dan 7 dimasukkan sebelum 8.

Tatasusunan yang terhasil akan menjadi:

2 5 7 8 9 10 20 30

Dengan cara ini, semua elemen tatasusunan diisih menggunakan isihan sisipan, memulakan perbandingan dengan elemen sebelumnya.

Contoh untuk Melaksanakan Isih Sisipan dalam Java

Isih Sisipan dalam Java ialah algoritma pengisihan mudah yang sesuai untuk semua set data kecil.

Kod:

public class InsertionSort {
public static void insertionSort(int arr[]) { for (int j = 1; j < arr.length; j++) { int key = arr[j]; int i = j-1;
while ( (i > -1) && ( arr[i] > key ) ) { arr[i+1] = arr[i]; i--; }
arr[i+1] = key;
}
}
static void printArray(int arr[]) { int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i<len; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[]){ int[] arr1 = {21,18,15,23,52,12,61};
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
}
}

Output:

12 15 18 21 23 52 61

Penjelasan:

• Dalam atur cara Insertion Sort di atas, fungsi insertionSort() digunakan untuk mengisih elemen tatasusunan asal. Pengisihan bermula dari elemen kedua kerana elemen pertama menganggap untuk diisih dengan sendirinya. Jadi gelung 'j' bermula dari indeks 1 tatasusunan. 'i' ialah pembolehubah yang menjejaki indeks sebelum 'j' untuk membandingkan nilai.'
• kunci’ ialah pembolehubah yang memegang nilai elemen semasa yang akan disusun dalam kedudukan yang disusun. gelung while() dilaksanakan jika nilai semasa kurang daripada nilai paling kiri supaya peralihan elemen boleh diproses, dan pada akhirnya, penyisipan elemen semasa pada kedudukan yang betul boleh dilakukan. fungsi printArray() digunakan untuk akhirnya mencetak tatasusunan yang diisih.

1. Kes Terbaik

Dalam isihan sisipan, kes terbaik ialah apabila semua elemen tatasusunan sudah diisih. Oleh itu, apabila mana-mana elemen dibandingkan dengan elemen paling kirinya, ia sentiasa lebih besar, dan oleh itu tiada peralihan dan pemasukan elemen akan diproses. Dalam kes ini, kerumitan kes terbaik ialah linear, iaitu O(n).

2. Kes Terburuk

Dalam kod isihan sisipan di atas, kes yang paling teruk ialah apabila tatasusunan berada dalam susunan terbalik jadi setiap kali apabila elemen itu dibandingkan dengan elemen paling kirinya, ia sentiasa lebih kecil dan kemudian dibandingkan dengan semua elemen prosiding yang mengambil tempat dan peralihan dan penyisipan dilakukan. Dalam kes ini, kerumitan isihan sisipan ialah O(n^2).

3. Kes Purata

Walaupun dalam kes biasa, isihan sisipan mempunyai kerumitan O(n^2) yang mana sesetengah elemen tidak memerlukan peralihan, manakala beberapa elemen dialihkan daripada kedudukannya dan sisipan pada kedudukan yang betul dilakukan.

4. Penggunaan Terbaik

Isihan sisipan adalah terbaik untuk digunakan apabila saiz tatasusunan tidak begitu besar, atau hanya sebilangan kecil elemen perlu diisih di mana hampir semua elemen diisih dan hanya beberapa perubahan perlu dibuat. Isih sisipan ialah salah satu algoritma terpantas untuk tatasusunan saiz kecil, malah lebih pantas daripada Isih Pantas. Malah, quicksort menggunakan Isihan Sisipan apabila mengisih bahagian kecil tatasusunannya.

Kesimpulan

Penjelasan di atas dengan jelas menunjukkan cara kerja dan pelaksanaan Insertion Sort dalam Java. Dalam bahasa pengaturcaraan lain juga, logik untuk melaksanakan Isihan Sisipan tetap sama hanya perubahan Sintaks. Sebelum melaksanakan sebarang algoritma pengisihan, adalah sangat penting untuk melakukan beberapa analisis terhadap senario di mana pengisihan perlu dilakukan kerana tidak setiap algoritma pengisihan sesuai dalam semua senario.

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