希爾排序，也稱遞減增量排序算法，是插入排序的壹種更高效的改進版本。但希爾排序是非穩定排序算法。
希爾排序是基於插入排序的以下兩點性質而提出改進方法的：
插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率； 但插入排序壹般來說是低效的，因為插入排序每次只能將數據移動壹位；
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若幹子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。
1. 算法步驟
選擇壹個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列個數 k，對序列進行 k 趟排序；
每趟排序，根據對應的增量 ti，將待排序列分割成若幹長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為壹個表來處理，表長度即為整個序列的長度。
2. 動圖演示
代碼實現 JavaScript 實例 function shellSort ( arr ) {
var len = arr. length ,
temp ,
gap = 1 ;
while ( gap 0 ; gap = Math . floor ( gap / 3 ) ) {
for ( var i = gap ; i = 0 && arr [ j ] > temp ; j -= gap ) {
arr [ j + gap ] = arr [ j ] ;
}
arr [ j + gap ] = temp ;
}
}
return arr ;
}
Python 實例 def shellSort ( arr ) :
import math
gap = 1
while ( gap 0 :
for i in range ( gap , len ( arr ) ) :
temp = arr [ i ]
j = i-gap
while j >= 0 and arr [ j ] > temp:
arr [ j+gap ] = arr [ j ]
j- = gap
arr [ j+gap ] = temp
gap = math . floor ( gap/ 3 )
return arr
Go 實例 func shellSort ( arr [] int ) [] int {
length := len ( arr )
gap := 1
for gap < length / 3 {
gap = gap * 3 + 1
}
for gap > 0 {
for i := gap ; i < length ; i ++ {
temp := arr [ i ]
j := i - gap
for j > = 0 && arr [ j ] > temp {
arr [ j + gap ] = arr [ j ]
j -= gap
}
arr [ j + gap ] = temp
}
gap = gap / 3
}
return arr
}
Java 實例 public static void shellSort ( int [ ] arr ) {
int length = arr. length ;
int temp ;
for ( int step = length / 2 ; step >= 1 ; step /= 2 ) {
for ( int i = step ; i = 0 && arr [ j ] > temp ) {
arr [ j + step ] = arr [ j ] ;
j -= step ;
}
arr [ j + step ] = temp ;
}
}
}
PHP 實例 function shellSort ( $arr )
{
$len = count ( $arr ) ;
$temp = 0 ;
$gap = 1 ;
while ( $gap 0 ; $gap = floor ( $gap / 3 ) ) {
for ( $i = $gap ; $i = 0 && $arr [ $j ] > $temp ; $j -= $gap ) {
$arr [ $j + $gap ] = $arr [ $j ] ;
}
$arr [ $j + $gap ] = $temp ;
}
}
return $arr ;
}
C 實例 void shell_sort ( int arr [ ] , int len ) {
int gap , i , j ;
int temp ;
for ( gap = len >> 1 ; gap > 0 ; gap >>= 1 )
for ( i = gap ; i = 0 && arr [ j ] > temp ; j -= gap )
arr [ j + gap ] = arr [ j ] ;
arr [ j + gap ] = temp ;
}
}
C++ 實例 template
void shell_sort ( T array [ ] , int length ) {
int h = 1 ;
while ( h = 1 ) {
for ( int i = h ; i = h && array [ j ] 0) { for (int i = gap; i arr.Length; i++) { int tmp = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > tmp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } gap /= 3; } } 以上為希爾排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等排序算法各有優缺點，用壹張圖概括：
關於時間復雜度
平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。
線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸並排序；
O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數。 希爾排序
線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。
關於穩定性
穩定的排序算法：冒泡排序、插入排序、歸並排序和基數排序。
不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
名詞解釋：
n：數據規模
k："桶"的個數
In-place：占用常數內存，不占用額外內存
Out-place：占用額外內存
穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同