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.
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].
Terdapat beberapa cara untuk menggunakan pengisihan sisipan - berikut ialah yang paling popular:
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]
Nota: jika anda mempunyai tatasusunan kosong atau singleton, ini dianggap diisih secara lalai.
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 antara arr[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 tatasusunan
1. 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){
Memandangkan anda mempunyai gelung yang berfungsi, tiba masanya untuk mencipta iterator yang akan mengisih semua elemen dalam susunan yang dikehendaki. Mulai sekarang, kami akan merujuk kepada iterator sebagai " 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 daripada jindeks
Sebaik sahaja kedua-dua syarat dalam gelung while adalah benar, nilai kunci tatasusunan akan sama dengan indeks j.
5. Mengisih tatasusunan
Selepas anda menyediakan gelung while, nilai jdan 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:
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.
Memandangkan anda sudah menguasai algoritma pengisihan ini, tiba masanya untuk menguji kemahiran teori dan praktikal anda. Kuiz teori #1 Anda diberi tatasusunan [1, 4, 6, 8] dan sedang menambah elemen baru n = 7 padanya. Apakah bilangan perbandingan yang perlu anda buat untuk mendapatkan urutan nombor yang diisih? Nyatakan nilai akhir indeks n dalam tatasusunan. Kuiz teori #2 Pada temu duga kerja, ketua pasukan meminta anda membuktikan bahawa sisipan isihan adalah kaedah yang tidak cekap. Diberi rentetan angka [0, 3, 6, 8, 9], apakah susunan urutan input anda untuk memaksimumkan masa berjalan yang diperlukan untuk mengisih? Masalah latihan Isih tatasusunan [0, 1, 4, 5, 2, 3, 7, 9, 8] dalam susunan menaik menggunakan isihan sisipan untuk Java.
Kesimpulan
Cabaran terbesar dalam memahami jenis sisipan adalah dalam memahami cara proses itu berfungsi. Sebaik sahaja anda menguasainya, menukar templat kepada kod adalah sekeping kek. Selagi anda berlatih dan menyemak semula masalah amalan yang berkaitan dari semasa ke semasa, anda akan meningkatkan kelajuan isihan sisipan anda dengan pantas.
Mari kita lihat lebih dekat pada input dan output jenis sisipan:
GO TO FULL VERSION