希爾排序

希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因D.L.Shell於1959年提出而得名。

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵字越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止。

基本介紹

• 中文名：希爾排序
• 外文名：Shell's Sort
• 別名：縮小增量排序
• 類型：插入排序
• 時間複雜度：O(n^（1.3—2）)
• 空間複雜度：O(1)
• 穩定性：不穩定

歷史

希爾排序按其設計者希爾（Donald Shell）的名字命名，該算法由1959年公布。一些老版本教科書和參考手冊把該算法命名為Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根據Metzner本人的說法，“我沒有為這種算法做任何事，我的名字不應該出現在算法的名字中。”

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

1. 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率。
2. 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位。

基本思想

先取一個小於n的整數d1作為第一個增量，把檔案的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2<d1重複上述的分組和排序，直至所取的增量=1(<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。

該方法實質上是一種分組插入方法

比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換。D.L.shell於1959年在以他名字命名的排序算法中實現了這一思想。算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。

一般的初次取序列的一半為增量，以後每次減半，直到增量為1。

給定實例的shell排序的排序過程

假設待排序檔案有10個記錄，其關鍵字分別是：

49，38，65，97，76，13，27，49，55，04。

增量序列的取值依次為：

5，2，1

希爾排序

穩定性

由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。

排序過程

縮小增量

希爾排序屬於插入類排序,是將整個有序序列分割成若干小的子序列分別進行插入排序。

排序過程：先取一個正整數d1<n，把所有序號相隔d1的數組元素放一組，組內進行直接插入排序；然後取d2<d1，重複上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止。

三趟結果

04 13 27 38 49 49 55 65 76 97

Shell排序

Shell排序的算法實現:

1． 不設監視哨的算法描述

void ShellPass(SeqList R，int d)

{//希爾排序中的一趟排序，d為當前增量

for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當前的有序區

if(R[ i ].key<R[i-d].key){

R[0]=R[i];j=i-d； //R[0]只是暫存單元，不是哨兵

do {//查找R的插入位置

R[j+d]=R[j]； //後移記錄

j=j-d； //查找前一記錄

}while(j>0&&R[0].key<R[j].key)；

R[j+d]=R[0]； //插入R到正確的位置上

} //endif

算法分析

優劣

不需要大量的輔助空間，和歸併排序一樣容易實現。希爾排序是基於插入排序的一種算法， 在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間複雜度與增量序列的選取有關，例如希爾增量時間複雜度為O(n²)，而Hibbard增量的希爾排序的時間複雜度為O()，希爾排序時間複雜度的下界是n*log2n。希爾排序沒有快速排序算法快 O(n(logn))，因此中等大小規模表現良好，對規模非常大的數據排序不是最優選擇。但是比O()複雜度的算法快得多。並且希爾排序非常容易實現，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞的情況下執行的效率會非常差。專家們提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快，再改成快速排序這樣更高級的排序算法. 本質上講，希爾排序算法是直接插入排序算法的一種改進，減少了其複製的次數，速度要快很多。 原因是，當n值很大時數據項每一趟排序需要移動的個數很少，但數據項的距離很長。當n值減小時每一趟需要移動的數據增多，此時已經接近於它們排序後的最終位置。 正是這兩種情況的結合才使希爾排序效率比插入排序高很多。Shell算法的性能與所選取的分組長度序列有很大關係。只對特定的待排序記錄序列，可以準確地估算關鍵字的比較次數和對象移動次數。想要弄清關鍵字比較次數和記錄移動次數與增量選擇之間的關係，並給出完整的數學分析，今仍然是數學難題。

時間性能

1．增量序列的選擇

Shell排序的執行時間依賴於增量序列。

好的增量序列的共同特徵：

① 最後一個增量必須為1；

② 應該儘量避免序列中的值(尤其是相鄰的值)互為倍數的情況。

有人通過大量的實驗，給出了較好的結果：當n較大時，比較和移動的次數約在nl.25到1.6n1.25之間。

2．Shell排序的時間性能優於直接插入排序

希爾排序的時間性能優於直接插入排序的原因：

①當檔案初態基本有序時直接插入排序所需的比較和移動次數均較少。

②當n值較小時，n和的差別也較小，即直接插入排序的最好時間複雜度O(n)和最壞時間複雜度0()差別不大。

③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由於已經按di-1作為距離排過序，使檔案較接近於有序狀態，所以新的一趟排序過程也較快。

因此，希爾排序在效率上較直接插入排序有較大的改進。

希爾分析

希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對於有序的序列效率很高。所以，希爾排序的時間複雜度會比o(n^2)好一些。

代碼實現

偽代碼

input: an array a of length n with array elements numbered 0 to n − 1
inc ← round(n/2)
while inc > 0 do:
for i = inc .. n − 1 do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc] > temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2.2)

Golang

func ShellSort(nums []int) []int{    //外層步長控制    for step := len(nums) / 2; step > 0; step /= 2 {        //開始插入排序        for i := step; i < len(nums); i++ {            //滿足條件則插入            for j := i - step; j >= 0 && nums[j+step] < nums[j]; j -= step {                nums[j], nums[j+step] = nums[j+step], nums[j]            }        }    }    return nums}

vb.net

Function Shell(Byval lines() As Integer) As Integer()    dim c() As Integer=lines.clone,div,i,j,k As Integer,Data As Integer    if UBound(c)=1 then return lines    For div=len/2 To 1        div/=2        For i=0 To div Step 1            For j=i To len-div                For k=j to len Step div                    If(data[j]>data[k])                    swapInt(data+j,data+k)                    End If                Next             Next         Next     NextEnd Function 

javascript

var arr = [49, 38, 65, 97, 76, 13, 27, 49, 55, 04];var len = arr.length;for (var fraction = Math.floor(len / 2); fraction > 0; fraction = Math.floor(fraction / 2)) {    for (var i = fraction; i < len; i++) {        for (var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction) {            var temp = arr[j];            arr[j] = arr[fraction + j];            arr[fraction + j] = temp;        }    }}console.log(arr);

pascal

const　size=12;type　arr=array[1..size]ofinteger;var　a:arr;　i,j,k,t:integer;procedure     DataInput;//生成隨機數列begin　    randomize;    for i:=1 to size do　        begin　            a[i]:=random(99)+1;            write(a[i]:3);        end;    writeln; end;procedure    DataOutput;//輸出begin　    for    i:=1    to    size    do　write(a[i]:3); end;procedure    insertionsort(var    a:arr);begin　    for    i:=2    to    size    do        begin　            t:=a[i];            j:=i-1;            while    (j>0)    and    (t<a[j])    do                begin　                    a[j+1]:=a[j];                    j:=j-1;                end;            a[j+1]:=t;        end;end;begin　   DataInput;    k:=size;    while    k>1    do　        begin　        k:=k    div    2;        for    j:=k+1    to    size    do　            begin　                t:=a[j];                i:=j-k;                while    (i>0)    and    (a[i]>t)    do　                begin　                    a[i+k]:=a[i];                    i:=i-k;                end;                a[i+k]:=t;            end;        end;     DataOutput;end.

Kotlin

fun sort(arr: IntArray) {    var gap = arr.size / 2    while (1 <= gap) {        for (i in gap..arr.size - 1) {            var j = i - gap            val tmp = arr[i]            while (j >= 0 && tmp < arr[j]) {                arr[j + gap] = arr[j]                j -= gap            }            arr[j + gap] = tmp        }        gap /= 2    }}

JAVA

public static void main(String [] args){    int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};        System.out.println("排序之前：");        for(int i=0;i<a.length;i++)        {            System.out.print(a[i]+" ");        }        //希爾排序        int d=a.length;            while(true)            {                d=d/2;                for(int x=0;x<d;x++)                {                    for(int i=x+d;i<a.length;i=i+d)                    {                        int temp=a[i];                        int j;                        for(j=i-d;j>=0&&a[j]>temp;j=j-d)                        {                            a[j+d]=a[j];                        }                        a[j+d]=temp;                    }                }                if(d==1)                {                    break;                }            }            System.out.println();            System.out.println("排序之後：");                for(int i=0;i<a.length;i++)                {                    System.out.print(a[i]+" ");                }    }

C#

using System;namespace ConsoleApplication8{    //希爾排序類    class ShellSorter    {        public void Sort(int[] list)        {      int _d = list.Length;            int _len = list.Length;            for (_d = _d / 2; _d > 0; )            {                if (_d % 2 == 0) _d++;                //按d分組                for (int i = 0; i < _d; i++)                {                    //每組執行直接插入排序算法                    for (int j = i + _d; j < _len; j += _d)                    {                        if (j < _len)                        {                            if (list[j] < list[j - _d])//後面小於前面                            {                                int temp = list[j];                                int k = 0;                                for (k = j - _d; k >= i && temp < list[k]; k -= _d)//比它大的元素後移動                                {                                    list[k + _d] = list[k];                                }                                list[k + _d] = temp;//插入最後比它小的後面                            }                        }                    }                }                Console.WriteLine("第一次d->" + _d);                for (int i = 0; i < _len; i++)                {                    Console.Write(string.Format("{0},", list[i]));                }                Console.WriteLine("");                _d = _d / 2;            }        }    }    public class MainClass    {        public static void Main(String[] args)        {            //模擬數據            int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };            ShellSorter sh = new ShellSorter();            sh.Sort(iArrary);            for (int m = 0; m <= 13; m++)            {                Console.WriteLine("{0}", iArrary[m]);            }            Console.ReadKey();        }    }}

C語言

#include<stdio.h>#include<math.h>#define MAXNUM 10void main(){    void shellSort(int array[],int n,int t);//t為排序趟數    int array[MAXNUM],i;    for(i=0;i<MAXNUM;i++)        scanf("%d",&array[i]);    shellSort(array,MAXNUM,(int)(log(MAXNUM+1)/log(2)));//排序趟數應為log2(n+1)的整數部分    for(i=0;i<MAXNUM;i++)        printf("%d ",array[i]);    printf("\n");}//根據當前增量進行插入排序void shellInsert(int array[],int n,int dk){    int i,j,temp;    for(i=dk;i<n;i++)//分別向每組的有序區域插入    {        temp=array[i];        for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比較與記錄後移同時進行            array[j+dk]=array[j];        if(j!=i-dk)            array[j+dk]=temp;//插入    }}//計算Hibbard增量int dkHibbard(int t,int k){    return (int)(pow(2,t-k+1)-1);}//希爾排序void shellSort(int array[],int n,int t){    void shellInsert(int array[],int n,int dk);    int i;    for(i=1;i<=t;i++)        shellInsert(array,n,dkHibbard(t,i));}//此寫法便於理解，實際套用時應將上述三個函式寫成一個函式。

C++

template <typename _RIter>void insert_sort(_RIter st, _RIter ed, int delta) {    for(_RIter i = st + delta; i < ed; i += delta) {        for(_RIter j = i; j > st; j -= delta)            if(*j < *(j - delta)) std::swap(*j, *(j - delta));            else break;    }}template <typename _RIter>void shell_sort(_RIter st, _RIter ed) {    for(int delta = ed - st; delta; delta /= 2)        for(int i = 0; i < delta; i++)            insert_sort(st + i, ed, delta);}

AS3

//需要排序的數組vararr:Array=[7,5,8,4,0,9];varsmall:int;//最小下標vartemp:int;for(vari:int=0;i<arr.length;i++){small=i;for(varj:int=i+1;j<arr.length+1;j++){if(arr[j]<arr[small]){small=j;}}if(small!=i){temp=arr[i];arr[i]=arr[small];arr[small]=temp;}trace(arr[i]);}

Ruby

def shell_sort(array)    gap = array.size    while gap > 1        gap = gap / 2          (gap..array.size-1).each do |i|            j = i            while j > 0                array[j], array[j-gap] = array[j-gap], array[j] if array[j] <= array[j-gap]                j -=  gap            end        end    end    arrayend

PHP

function shell_sort(&$arr) {    if(!is_array($arr)) return;    $n = count($arr);    for ($gap = floor($n/2); $gap > 0; $gap = floor($gap/=2)) {        for($i = $gap; $i < $n; ++$i) {            for($j = $i - $gap; $j >= 0 && $arr[$j + $gap] < $arr[$j]; $j -= $gap) {                $temp = $arr[$j];                $arr[$j] = $arr[$j + $gap];                $arr[$j + $gap] = $temp;            }        }    }}

Python

def shell(arr): n=len(arr) h=1 while h<n/3:  h=3*h+1 while h>=1:  for i in range(h,n):   j=i   while j>=h and arr[j]<arr[j-h]:    arr[j], arr[j-h] = arr[j-h], arr[j]    j-=h  h=h//3 print arr