希爾排序(Shell’s Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序演算法的一種更高效的改進版本，希爾排序是非穩定排序演算法，該方法因 D.L.Shell 于 1959 年提出而得名，
上面的這段敘述來自百度百科，我們可以知道希爾排序是插入排序的改進版，如果插入排序還沒有搞清楚的話，建議先去看這篇博客補一補：都是??兩層回圈??的冒泡排序，選擇排序，插入排序該怎么區分，這里我們也大致在對插入排序做個復習，
插入排序將第一個數（也可以識別的）看為有序區間開展，從第二個數開始依次拿著每個數去到有序區間依次比較，最終插入到合適他的地方，
希爾排序做了升級，遵循下面這個回圈：
- 按照一個規則將待排序序列分組（分組規則有很多，我們這里介紹一種：開始將序列分成序列長度除以二組，比如一共十個數，除以二等于五，就先分成5組，兩個為一組，然后每次回圈都會重新除以二分組，第二次就是 5 / 2向下取整為2組，第三次是一組）
- 然后對同一組做組內插入排序，我們做升序
- 組數除以二，現在就是2組，就是五個為一組
- 回到2回圈
一直到所有數為同一組，再做最后一次排序，最后一次就是我們理解的對整個序列插入排序，這次排序結束序列也就有序了，下面看一下動圖演示：
可以清楚地看到最后一次就是我們原來學的插入排序，那么有些人就有疑問了，為什么要大費周章的先從分組做插入排序開始？因為這樣做會讓每個數字更快的接近他排好序的位置，從而節省了時間，可以直白的理解為這么做就是更快了，，，
下面是代碼實作：
public static void insertSort(int[] array, int size){
for (int i = size; i < array.length; i++){
int j;
int val = array[i];
for (j = i - size; j >= 0 && val < array[j]; j -= size){
array[j +size] = array[j];
}
array[j + size] = val;
}
}
public static void shellSort(int[] array){
int size = array.length / 2;
while (true){
insertSort(array, size);
if (size == 1){
break;
}
size /= 2;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/296642.html
標籤：其他