希爾排序

希爾排序

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

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

基本介紹

  • 中文名:希爾排序
  • 外文名:Shell's Sort
  • 別名:縮小增量排序
  • 類型插入排序
  • 時間複雜度:O(n^(1.3—2))
  • 空間複雜度:O(1)
  • 穩定性:不穩定
歷史,基本思想,穩定性,排序過程,縮小增量,Shell排序,算法分析,優劣,時間性能,希爾分析,代碼實現,偽代碼,Golang,vb.net,javascript,pascal,Kotlin,JAVA,C#,C語言,C++,AS3,Ruby,PHP,Python,

歷史

希爾排序按其設計者希爾(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(n2),而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

相關詞條

熱門詞條

聯絡我們