Menyusun tatasusunan ialah salah satu operasi yang paling biasa yang perlu diketahui oleh pemula Java. Walaupun tatasusunan bukanlah cara yang paling mudah untuk menyusun data dan ini kebanyakannya terpakai kepada nombor kecil, konsep di sebalik pengisihan tatasusunan mempunyai banyak aplikasi dalam perisian yang kompleks dan sains data. Dalam siaran ini, kita akan melihat dengan lebih dekat apakah jenis sisipan. Kami menyertakan beberapa contoh dan masalah amalan untuk membantu anda memahami sepenuhnya konsep ini.
![Isih Sisipan dalam Java - 1]()
Mari kita lihat lebih dekat pada input dan output jenis sisipan:
Apakah Isih Sisipan?
Pada asasnya, isihan sisipan ialah algoritma yang digunakan pembangun untuk menyusun rentetan nombor kecil. Ia membahagikan semua nilai kepada dua tindanan - satu disusun dan tidak diisih. Satu demi satu, nombor dalam timbunan "tidak diisih" dipilih dan diletakkan dalam susunan yang betul.
Mari kita lihat lebih dekat pada input dan output jenis sisipan:
- Input: tatasusunan A dengan unsur angka tidak diisih: A[0,1, n, n-2...].
- Output: tatasusunan yang mengandungi nombor yang sama tetapi diisih sepenuhnya. Yang ini biasanya dirujuk sebagai B: B[0]B[1]...B[n-1].
- Isih berangka (tertib bertambah): [1, 2, 3, 4, 5]
- Isih berangka (tertib menurun): [5, 4, 3, 2, 1]
- Pengisihan mengikut abjad: [a, b, c, d]
Memahami Teori Isih Sisipan
Sebelum meneroka kod di sebalik jenis sisipan, mari kita pecahkan algoritma menggunakan bahasa bukan teknikal. Oleh kerana kami akan menunjukkan kod untuk mengisih dalam tertib menaik, adalah wajar untuk menerangkan algoritma langkah demi langkah dalam siaran ini. Langkah 1. Mengulang antaraarr[1]dan arr[n]di mana nnilai berangka biasanya kurang daripada 10. Langkah 2. Bandingkan elemen yang anda pilih (dikenali sebagai key) dengan nombor sebelumnya dalam jujukan menggunakan sort()kaedah. Langkah 3. Jika semua elemen lebih kecil daripada penggantinya, ulangi perbandingan sehingga anda menemui nilai yang lebih besar. Langkah 4. Tukar nilai yang lebih besar satu kedudukan di luar yang lebih kecil untuk mencipta urutan tertib. Langkah 5. Ulangi proses sehingga anda mendapat rentetan aksara yang diisih
Mengisih tatasusunan primitif
Memandangkan algoritma adalah salah satu operasi Java yang paling mudah, walaupun pemula yang lengkap tidak sepatutnya menghadapi banyak masalah untuk melaksanakannya. Berikut ialah panduan langkah demi langkah untuk mengisih tatasusunan1. Isytihar tatasusunan untuk pengisihan
Sebagai permulaan, mari buat rentetan nilai yang akan kami paparkan kemudian menggunakan Java. Untuk menggunakan isihan sisipan, anda perlu mencipta tatasusunan. Untuk itu, gunakanint[]
int[] arrayA = {10, 14, 20, 30};
2. Gunakan sort_arr untuk melaksanakan algoritma
Kaedah sort_arr ialah salah satu cara yang paling biasa untuk melaksanakan isihan sisipan. Dalam amalan, ia kelihatan seperti ini:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Buat gelung dan lelaran
Dengan menggunakan gelung dalam algoritma isihan sisipan, pembangun tidak perlu mengulang logik untuk setiap elemen. Walaupun membuat gelung kelihatan rumit, ia agak mudah - berikut ialah contoh:
for(int i=0; i< sort_arr.length; ++i){
j".
int j = i;
4. Mencipta "gelung sementara"
Apabila ia datang kepada isihan sisipan, gelung "semasa" adalah penting untuk tatasusunan baru yang diisih. Untuk menyediakannya untuk isihan sisipan tertib menaik, pembangun perlu mematuhi dua syarat:- Nilai yang diberikan kepada j mestilah lebih besar daripada 0
- Nilai yang ditetapkan
j-1perlu lebih besar daripadajindeks
j.
5. Mengisih tatasusunan
Selepas anda menyediakan gelung while, nilaijdan j-1akan ditukar sehingga satu atau kedua-dua syarat dalam gelung while gagal. Begitu juga, pengisihan akan diulang untuk setiap nilai dalam gelung for sehingga keadaan gelung untuk juga gagal. Begini cara proses isihan sisipan berfungsi dalam amalan:
int key = sort_arr[j];
sort_arr[j] = sort_arr[j-1];
sort_arr[j-1] = key;
j = j-1;
Mengisih ArrayList
Walaupun memahami matematik di sebalik isihan sisipan adalah penting, apabila ia berkaitan dengan pembangunan perisian kehidupan sebenar, anda akan menyusun ArrayLists lebih daripada urutan dalam tatasusunan primitif. Berikut ialah panduan langkah demi langkah untuk mengisih ArrayList:- Buat kelas baharu
Elementuntuk item yang dimiliki oleh koleksi.public class Element { private int id; public Element(int id) { this.id = id; } - Dalam koleksi, terdapat
compareTo()kaedah - kami akan menggunakan ini untuk membandingkan id dua elemen.public int compareTo(Element element) { int res = 0; if (this.id < element.getId()) { res = -1; } if (this.id > element.getId()) { res = 1; } return res; } } - Gunakan algoritma dan buat beberapa gelung untuk mengisih objek
ArrayListdan bukannya membandingkannya.public static void insertionSortArrayList(List<element> list) { for (int j = 1; j < list.size(); j++) { Element current = list.get(j); int i = j-1; while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) { list.set(i+1, list.get(i)); i--; } list.set(i+1, current); } } - Anda boleh menambah lebih banyak elemen juga
ArrayList, seperti yang ditunjukkan di bawah:List<element> list = new ArrayList<>(); // Create elements w/ IDs 0-24 for (int i = 0; i < 25; i++) { list.add(new Element(i)); } // To use insertion sort, shuffle the values Collections.shuffle(list); - Kini tiba masanya untuk menyusun:
// This helps print values before sorting list.forEach(e -> System.out.print(e.getId() + ", ")); // Sort the list insertionSortArrayList(list); System.out.println(); // Display a sorted array list.forEach(e -> System.out.print(e.getId() + ", ")); - Sekarang mari kita bandingkan input dan output untuk memastikan kita tidak membuat kesilapan. Berikut ialah perbandingan rentetan yang kami gunakan sebagai contoh.
4, 2, 6, 7, 0, 5, 9, 1, 8, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
GO TO FULL VERSION