Perkenalan
Penyortiran bukit (Mengurangi metode tambahan) termasuk dalam penyortiran kelas penyisipan. Itu diusulkan oleh shell. Penyortiran bukit telah membuat perbaikan sederhana untuk penyortiran penyisipan langsung: Ini meningkatkan interval antara elemen dalam penyortiran penyisipan dan menyisipkan ke dalam elemen interval ini, sehingga menyebabkan item data bergerak melintasi rentang besar. Setelah item data ini diurutkan satu kali, algoritma penyortiran bukit mengurangi interval item data dan kemudian mengurutkannya, dan hasilnya pada gilirannya. Interval antara item data ketika penyortiran ini disebut peningkatan, dan huruf H digunakan untuk mewakili kenaikan ini.
Urutan H yang umum digunakan diusulkan oleh Knuth. Urutan ini dimulai dari 1 dan dihasilkan oleh rumus berikut:
h = 3 * h +1
Program pada gilirannya perlu menghitung urutan H secara terbalik, dan harus digunakan
h = (h-1)/3
Implementasi Kode
Kode Implementasi 1:
public static void shellsort (int [] arr) {int temp; for (int delta = arr.length/2; delta>=1; delta/=2){ //Sort each increment once for (int i=delta; i<arr.length; i++){ for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //Note that the increment and difference are delta temp = arr[j-delta]; arr [j-delta] = arr [j]; arr [j] = temp; }} // loop i} // loop delta}Kode Implementasi 2:
public static void shellsort2 (int [] arr) {int delta = 1; while (delta <arr.length/3) {// menghasilkan delta delta = delta*3+1; // <o (n^(3/2)) oleh Knuth, 1973>: 1, 4, 13, 40, 121, ...} int temp; untuk (; delta> = 1; delta/= 3) {untuk (int i = delta; i <arr.length; i ++) {for (int j = i; j> = delta && arr [j] <arr [j-delta]; j- = delta) {temp = arr [j-delta]; arr [j-delta] = arr [j]; arr [j] = temp; }} // loop i} // loop delta} Ketika program di atas membandingkannya dengan metode penyisipan langsung, Anda akan menemukan bahwa perbedaan antara itu dan sortir penyisipan langsung adalah bahwa H dalam jenis penyisipan langsung akan digantikan oleh 1.
Penyortiran shell tidak stabil, overhead ruangnya juga O (1), dan overhead waktu diperkirakan antara O (N3/2) dan O (N7/6).