站長資訊網(wǎng)希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：
- 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率；
- 但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位；
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄”基本有序”時，再對全體記錄進行依次直接插入排序。
1. 算法步驟
選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列個數(shù) k，對序列進行 k 趟排序；
每趟排序，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
2. 動圖演示
代碼實現(xiàn)
JavaScript
實例
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //動態(tài)定義間隔序列
gap =gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i–gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
Python
實例
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+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
實例
length := len(arr)
gap := 1
for gap < gap/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
實例
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int gap = 1;
while (gap < arr.length) {
gap = gap * 3 + 1;
}
while (gap > 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 = (int) Math.floor(gap / 3);
}
return arr;
}
}
PHP
實例
{
$len = count($arr);
$temp = 0;
$gap = 1;
while($gap < $len / 3) {
$gap = $gap * 3 + 1;
}
for ($gap; $gap > 0; $gap = floor($gap / 3)) {
for ($i = $gap; $i < $len; $i++) {
$temp = $arr[$i];
for ($j = $i – $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
$arr[$j+$gap] = $arr[$j];
}
$arr[$j+$gap] = $temp;
}
}
return $arr;
}
C
實例
int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1)
for (i = gap; i < len; i++) {
temp = arr[i];
for (j = i – gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}
C++
實例
void shell_sort(T array[], int length) {
int h = 1;
while (h < length / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h && array[j] < array[j – h]; j –= h) {
std::swap(array[j], array[j – h]);
}
}
h = h / 3;
}
}
參考地址：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/4.shellSort.md
https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
