Jenis Shell adalah algoritma penyortiran yang sangat "ajaib". Dikatakan "ajaib" karena tidak ada yang dapat dengan jelas menjelaskan apa yang sebenarnya dapat dicapai oleh kinerjanya. Memilah -milah bukit karena dl. Shell dinamai setelah itu diusulkan pada tahun 1959. Karena mobil Hoare mengusulkan penyortiran cepat pada tahun 1962, umumnya digunakan penyortiran cepat karena lebih sederhana. Namun, banyak ahli matematika masih tanpa lelah mencari kompleksitas penyortiran bukit terbaik. Sebagai programmer biasa, kita dapat mempelajari ide -ide Hill.
Ngomong -ngomong, sebelum penyortiran Hill muncul, ada pandangan umum di dunia komputer bahwa "algoritma penyortiran tidak dapat menerobos O (n2)". Munculnya penyortiran bukit mematahkan kutukan ini, dan segera, algoritma seperti penyortiran cepat dirilis satu demi satu. Dalam hal ini, penyortiran bukit membawa kita ke era baru.
Tinjauan/Ide Algoritma
Proposal penyortiran bukit terutama didasarkan pada dua poin berikut:
1. Algoritma penyortiran penyisipan kira -kira dapat mencapai kompleksitas O (n) dan sangat efisien ketika array pada dasarnya dipesan.
2. Namun, penyisipan penyisipan hanya dapat memindahkan data dengan satu bit pada satu waktu, dan kinerjanya akan memburuk dengan cepat ketika array besar dan pada dasarnya tidak teratur.
Berdasarkan ini, kita dapat menggunakan metode penyortiran insert yang dikelompokkan, yang merupakan metode spesifik: (ambil array 16 elemen sebagai contoh)
1. Pilih delta tambahan, yang lebih besar dari 1, dan pilih subarray dari array dengan kenaikan ini untuk penyortiran penyisipan langsung. Misalnya, jika kenaikan 5 dipilih, elemen dengan subskrip 0, 5, 10, 15 diurutkan.
2. Simpan Delta Penambahan dan pindahkan elemen pertama pada gilirannya untuk penyisipan dan penyortiran sampai putaran selesai. Untuk contoh di atas, array [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] diurutkan secara bergantian.
3. Kurangi kenaikan dan ulangi proses di atas secara terus menerus sampai kenaikan berkurang menjadi 1. Jelas, terakhir kali adalah jenis insert langsung.
4. Penyortiran selesai.
Seperti yang dapat dilihat dari hal -hal di atas, kenaikannya terus berkurang, jadi penyortiran bukit sekali lagi disebut "pengurangan penyortiran tambahan".
Implementasi Kode
Sortir Paket; Public Class ShellSortTest {Public Static Int Count = 0; public static void main (string [] args) {int [] data = int int [] {5, 3, 6, 2, 1, 9, 4, 8, 7}; cetak (data); shellsort (data); cetak (data); } public static void shellsort (int [] data) {// Hitung nilai h nilai h = 1; while (h <= data.length / 3) {h = h * 3 + 1; } while (h> 0) {for (int i = h; i <data.length; i += h) {if (data [i] <data [i - h]) {int tmp = data [i]; int j = i - h; while (j> = 0 && data [j]> tmp) {data [j + h] = data [j]; j -= h; } data [j + h] = tmp; cetak (data); }} // Hitung nilai h berikutnya h = (h - 1) / 3; }} public static void print (int [] data) {for (int i = 0; i <data.length; i ++) {System.out.print (data [i]+"/t"); } System.out.println (); }} Hasil Menjalankan:
5 3 6 2 1 9 4 8 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 9
Kinerja/kompleksitas algoritma
Urutan tambahan yang diurutkan oleh Hill dapat diambil kapan saja, dan satu -satunya persyaratan adalah bahwa yang terakhir harus 1 (karena perlu untuk memastikan bahwa itu dipesan oleh 1). Namun, pemilihan urutan yang berbeda akan memiliki dampak besar pada kinerja algoritma. Kode di atas menunjukkan dua peningkatan.
Ingat: Yang terbaik adalah tidak memiliki faktor umum selain 1 untuk setiap dua elemen dalam urutan tambahan! (Jelas, menyortir 2 secara berurutan tidak terlalu bermakna).
Di bawah ini adalah beberapa urutan tambahan yang umum.
Penambahan pertama adalah yang awalnya diusulkan oleh Donald Shell, yaitu, lipatan dikurangi menjadi 1. Menurut penelitian, menggunakan kenaikan bukit, kompleksitas waktu masih O (N2).
Kenaikan kedua hibbard: {1, 3, ..., 2^k-1}. Kompleksitas waktu dari urutan tambahan ini kira -kira O (n^1.5).
Peningkatan Sedgewick Increment ketiga: (1, 5, 19, 41, 109, ...), yang menghasilkan urutan baik 9*4^i - 9*2^i + 1 atau 4^i - 3*2^i + 1.
Stabilitas algoritma
Kita semua tahu bahwa penyerapan penyisipan adalah algoritma yang stabil. Namun, penyortiran shell adalah proses beberapa penyisipan. Dalam satu penyisipan kita dapat memastikan bahwa urutan elemen yang sama tidak dipindahkan, tetapi dalam beberapa insersi, sangat mungkin bahwa elemen yang sama dipindahkan dalam putaran penyisipan yang berbeda, dan stabilitas akhirnya dihancurkan. Oleh karena itu, penyortiran shell bukanlah algoritma yang stabil.
Algoritma skenario yang berlaku
Meskipun penyortiran shell cepat, ia menyisipkan penyortiran, dan urutan besarnya tidak sebagus bintang yang naik - penyortiran cepat O (NN) cepat. Penyortiran shell bukanlah algoritma yang baik dalam menghadapi sejumlah besar data. Namun, sangat mungkin untuk menggunakan data kecil dan menengah.