希爾排序的基本原理

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}

排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是希爾排序算法：

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率；但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位；

希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄"基本有序"時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

1. 算法步驟

選擇一個(gè)增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；

每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

2. 動(dòng)圖演示

代碼實(shí)現(xiàn)JavaScript實(shí)例 function shellSort(arr) {? ? var len = arr.length,? ? ? ? temp,? ? ? ? gap = 1;? ? while(gap < len/3) { ? ? ? ? ?//動(dòng)態(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實(shí)例 def shellSort(arr):? ? 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 arrGo實(shí)例 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實(shí)例 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 < length; i++) {? ? ? ? ? ? temp = arr[i];? ? ? ? ? ? int j = i - step;? ? ? ? ? ? while (j >= 0 && arr[j] > temp) {? ? ? ? ? ? ? ? arr[j + step] = arr[j];? ? ? ? ? ? ? ? j -= step;? ? ? ? ? ? }? ? ? ? ? ? arr[j + step] = temp;? ? ? ? }? ? }}PHP實(shí)例 function shellSort($arr){? ? $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實(shí)例 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 < 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++實(shí)例 templatevoid 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

以下是熱心網(wǎng)友對(duì)希爾排序算法的補(bǔ)充，僅供參考：

熱心網(wǎng)友提供的補(bǔ)充1：

我看這個(gè)沒把 C# 版本寫出來，我寫了一下，下面是 C# 版本：

static void ShellSort(int[] arr)
{
    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 /= 3;
    }
}

以上為希爾排序算法詳細(xì)介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點(diǎn)，用一張圖概括：

關(guān)于時(shí)間復(fù)雜度

平方階 (O(n2)) 排序 各類簡(jiǎn)單排序：直接插入、直接選擇和冒泡排序。

線性對(duì)數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。 希爾排序

線性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。

關(guān)于穩(wěn)定性

穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。

不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數(shù)據(jù)規(guī)模

k："桶"的個(gè)數(shù)

In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存

Out-place：占用額外內(nèi)存

穩(wěn)定性：排序后 2 個(gè)相等鍵值的順序和排序之前它們的順序相同