反饋

希爾排序

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

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

中文名: 希爾排序
外文名: Shell's Sort
別名: 縮小增量排序

類型: 插入排序
空間複雜度: O(1)
穩定性: 不穩定

希爾排序發展歷史

Donald Shell, 1924-2015

希爾排序按其設計者希爾（Donald Shell）的名字命名，該算法由希爾在 1959 年所發表的論文“A high-speed sorting procedure”^[2] 中所描述。

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

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

1961年，IBM 公司的女程序員 Marlene Metzner Norton（瑪琳·梅茨納·諾頓）首次使用 FORTRAN 語言編程實現了希爾排序算法。在其程序中使用了一種簡易有效的方法設置希爾排序所需的增量序列：第一個增量取待排序記錄個數的一半，然後逐次減半，最後一個增量為 1。該算法後來被稱為 Shell-Metzner 算法^[3] ，Metzner 本人在2003年的一封電子郵件中説道：“我沒有為這種算法做任何事，我的名字不應該出現在算法的名字中。”^[4]

希爾排序基本思想

先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2 =1(

…)

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

比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換。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數組元素放一組，組內進行直接插入排序；然後取d2

三趟結果

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

if(R[ i ].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+d]=R[0]； //插入R到正確的位置上

} //endif

希爾排序算法分析

希爾排序優劣

不需要大量的輔助空間，和歸併排序一樣容易實現。希爾排序是基於插入排序的一種算法，在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間的時間複雜度為O(

)，希爾排序時間複雜度的下界是n*log2n。希爾排序沒有快速排序算法快 O(n(logn))，因此中等大小規模表現良好，對規模非常大的數據排序不是最優選擇。但是比O(

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

希爾排序時間性能

1．增量序列的選擇

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

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

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

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

有人通過大量的實驗，給出了較好的結果：當n較大時，比較和移動的次數約在n^1.25到(1.6n)^1.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 += step {
            //滿足條件則插入
            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
     Next
End 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 += fraction) {
        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[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
	System.out.println("排序之前：");
	for(int i=0;i<array.length;i++){
		System.out.print(array[i]+" ");
	}
  	//希爾排序
	int gap = array.length;
    while (true) {    
		gap /= 2;   //增量每次減半    
		for (int i = 0; i < gap; i++) {        
			for (int j = i + gap; j < array.length; j += gap) {//這個循環裏其實就是一個插入排序                       
				int k = j - gap;            
				while (k >= 0 && array[k] > array[k+gap]) {
					int temp = array[k];
					array[k] = array[k+gap];
					array[k + gap] = temp;                
					k -= gap;            
				}                
			}    
		}    
  		if (gap == 1)        
			break;
	}

	System.out.println();
    System.out.println("排序之後：");
	for(int i=0;i<array.length;i++){
		System.out.print(array[i]+" ");
	}
}

希爾排序C#

using System;
using System.Collections.Generic;

namespace Demo
{
    class Program
    {
        public static List<int> ShellSort(List<int> data)
        {
            for (int gap = data.Count / 2; gap > 0; gap = gap / 2) {
                for (var i = gap; i < data.Count; i++) {
                    var j = i;
                    var current = data[i];
                    while (j - gap >= 0 && current < data[j - gap]) {
                        data[j] = data[j - gap];
                        j = j - gap;
                    }
                    data[j] = current;
                }
            }
            return data;
        }

        public static void Main(String[] args)
        {
            var iArray = new List<int> { 1, 5, 3, 6, 10, 55, 55, 100, 9, 2, 87, 12, 34, 75, 33, 47 };
            var newArray = ShellSort(iArray);
            Console.WriteLine(string.Join(",", newArray));
        }
    }
}

希爾排序C語言

#include<stdio.h>
#include<math.h>

#define MAXNUM 10

void shellSort(int array[],int n,int t);//t為排序趟數

void main()
{
    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

//需要排序的數組
var arr:Array = [7, 5, 8, 4, 0, 9];
var small:int;//最小下標
var temp:int;
for(var i:int = 0; i < arr.length; i++){
	small = i;
	for(var j: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  
  array
end

希爾排序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;
            }
        }
    }
}

希爾排序Python3.x

def shell_sort(seq):
    """
    希爾排序
    思想：通過控制增量將序列分組，組內直接插入排序完再縮小增量再分組排序，
    如8個序列，最初增量為8/2=4，所以1~4為一組，5~8為一組，1-5比較、2-6比較、
    3-7比較、4-8比較，此時組內比較再增量/2分組，直到最後增量為1時排序次數就少很多
    :param seq: 待排序的序列
    :return:
    """
    seq_len = len(seq)
    step = seq_len >> 1
    # 增量小於1説明最終排序已完成
    while step:
        for i in range(step, seq_len):
            # j記錄元素原始位置，用於查找前面所有小於當前元素的元素
            j = i
            while seq[j] < seq[j-step] and j-step >= 0:
                seq[j], seq[j-step] = seq[j-step], seq[j]
                # 改變下標，查看前面是否還有更小的值
                j -= step
        print(f"增量{step}的排序：", seq)
        # 每次增長減小一半
        step = step >> 1

希爾排序Objective-C

+ (NSArray *)shellSort:(NSArray *)unsortDatas {
    NSMutableArray *unSortArray = [unsortDatas mutableCopy];
    int len = (int)unSortArray.count; 
    for (int gap = floor(len / 2); gap > 0; gap = floor(gap/2)) {
        for (int i = gap; i < len; i++) {
            for (int j = i - gap; j >= 0 && [unSortArray[j] integerValue] > [unSortArray[j+gap] integerValue]; j-=gap) {
                NSNumber *temp = unSortArray[j];
                unSortArray[j] = unSortArray[gap+j];
                unSortArray[gap+j] = temp;
            }
        }
    }
    return [unSortArray copy];
}

希爾排序Rust

pub fn shell_sort(nums:&Vec<i32>)->Vec<i32>{
    let mut nums = nums.to_vec();
    fn insertion(nums: &mut Vec<i32>, start: usize, gap: usize) {
        for i in ((start + gap)..nums.len()).step_by(gap) {
            let val_current = nums[i];
            let mut pos = i;
            // make swaps
            while pos >= gap && nums[pos - gap] > val_current {
                nums[pos] = nums[pos - gap];
                pos = pos - gap;
            }
            nums[pos] = val_current;
        }
    }
    let mut count_sublist = nums.len() / 2; // makes gap as long as half of the array
    while count_sublist > 0 {
        for pos_start in 0..count_sublist {
            insertion(&mut nums, pos_start, count_sublist);
        }
        count_sublist /= 2; // makes gap as half of previous
    }
    return  nums
}

參考資料

1. 嚴蔚敏，吳偉民．數據結構（c語言版）：清華大學出版社，1997.4
2. https://dl.acm.org/doi/10.1145/368370.368387 ．ACM Digital Library[引用日期2021-12-17]
3. Shell-Metzner Sort ．GeeksforGeeks[引用日期2021-12-17]
4. Shell Sort ．NIST（美國國家標準技術研究所）[引用日期2021-12-17]

希爾排序的概述圖（2張）

詞條統計

瀏覽次數：次
編輯次數：175次歷史版本
最近更新：泡沫之夏吹泡泡（2024-02-18）