希爾排序分析
希爾(Shell)排序又稱為縮小增量排序，它是一種插入排序，它是直接插入排序演算法的一種威力加強版，
主要是為了解決插入排序中，在集合前面有序元素過多時導致的重復無用回圈的問題，
由于屬于插入排序的變種，故基本原理也是插入排序的原理，將整個集合分為有序以及無無序兩個部分，然后從無序部分中不斷取出元素放入有序集合部分，
但是希爾排序引入了一個叫步長（gap）的概念，本質是將集合分組，
希爾排序是不穩定的，即兩個相同的元素相對位置，在排序后可能會發生變化，
如圖：
步驟分析
- 將長度為10的集合分為 10/2 = 5 組，這五組各自有兩個元素，分別對每個組內的這兩個元素進行插入排序，
在這一步之后 ，若集合本身前面是有序的，只是后面有些無序序列時，此時的無序序列也已經會被前移到前半部分了
- 繼續縮小步長（縮小一倍），再次分批進行插入排序，直至步長為1，再次進行最后一次插入排序，可以有效降低插入排序的無效次數
JAVA代碼實作：
/**
* 希爾排序（插入排序變種）
* <p>
* 為了改善插入排序的一些弊端，比如原陣列本來在前面就有很多的有序元素，插入排序前面的很多遍歷就都成為了徒勞，對程式的浪費
* 希爾排序會將集合先進行分組，先按每組來排序，然后減小分組，繼續進行插入排序，直至分組數小于0
* [4, 2, 17, 3, 85, 0, 31, 2, 7, 61, 43, 87, 31, 39, 38, 42, 72, 24, 20, 55]
* 20個元素，首先分10組，其中，下標位0，10是一組，1，11 是一組，2，12是一組，，，，
* 第二次，分5組，下表0，5，10，15為一組，1，6，11，16是一組，，，，
* 第三次，分2組，下表0，2，4，6，8，10，12，14，16，18為一組，1，3，5，7，9，11，13，15，17，19 為一組
* 最后分組數為1，進行整體插入排序
*
* @param arr
*/
public void shellOrder(int[] arr) {
int buc = arr.length / 2;
while (buc > 0) {
for (int x = buc; x < arr.length; x++) {
int cur = arr[x];
for (int y = x - buc; y < x; y += buc) {
if (arr[y] > cur) {
int temp = arr[y];
arr[y] = cur;
arr[x] = temp;
break;
}
}
}
buc = buc / 2;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262120.html
標籤：其他
上一篇：「1s」即可！用 VS Code 一鍵玩轉 GitHub 代碼！
下一篇：ZZULIOJ 1185