本页使用了标题或全文手工转换

希尔排序

维基百科,自由的百科全书
跳到导航 跳到搜索
希尔排序
Step-by-step visualisation of Shellsort
以23, 10, 4, 1的步長序列進行希爾排序。
分类 排序算法
数据结构 數組
最坏时间复杂度 根據步長序列的不同而不同。已知最好的:
最优时间复杂度 O(n)
平均时间复杂度 根據步長序列的不同而不同。
最坏空间复杂度 O(n)
希爾排序算法彩條

希爾排序(Shellsort),也稱遞減增量排序算法,是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。

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

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

歷史[编辑]

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

算法實現[编辑]

原始的算法實現在最壞的情況下需要進行O(n2)的比較和交換。 V. Pratt的書[1]對算法進行了少量修改,可以使得性能提升至O(n log2 n)。這比最好的比較算法的O(n log n)要差一些。

希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後算法再取越來越小的步長進行排序,算法的最後一步就是普通的插入排序,但是到了這步,需排序的數據幾乎是已排好的了(此時插入排序較快)。

假設有一個很小的數據在一個已按升序排好序的數組的末端。如果用複雜度為O(n2)的排序(冒泡排序插入排序),可能會進行n次的比較和交換才能將該數據移至正確位置。而希爾排序會用較大的步長移動數據,所以小數據只需進行少數比較和交換即可到正確位置。

一個更好理解的希爾排序實現:將數組列在一個表中並對列排序(用插入排序)。重複這過程,不過每次用更長的列來進行。最後整個表就只有一列了。將數組轉換至表是為了更好地理解這算法,算法本身僅僅對原數組進行排序(通過增加索引的步長,例如是用i += step_size而不是i++ )。

例如,假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我們以步長為5開始進行排序,我們可以通過將這列表放在有5列的表中來更好地描述算法,這樣他們就應該看起來是這樣:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然後我們對每列進行排序:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

將上述四行數字,依序接在一起時我們得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了,然後再以3為步長進行排序:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之後變為:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最後以1步長進行排序(此時就是簡單的插入排序了)。

步長序列[编辑]

步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。算法最開始以一定的步長進行排序。然後會繼續以一定步長進行排序,最終算法以步長為1進行排序。當步長為1時,算法變為普通插入排序,這就保證了數據一定會被排序。

Donald Shell最初建議步長選擇為並且對步長取半直到步長達到1。雖然這樣取可以比類的算法(插入排序)更好,但這樣仍然有減少平均時間和最差時間的餘地。可能希爾排序最重要的地方在於當用較小步長排序後,以前用的較大步長仍然是有序的。比如,如果一個數列以步長5進行了排序然後再以步長3進行排序,那麼該數列不僅是以步長3有序,而且是以步長5有序。如果不是這樣,那麼算法在迭代過程中會打亂以前的順序,那就不會以如此短的時間完成排序了。

步長序列 最壞情況下複雜度

已知的最好步長序列是由Sedgewick提出的(1, 5, 19, 41, 109,...),該序列的項來自這兩個算式/lydia.sinapova/www/cmsc250/LN250_Weiss/L12-ShellSort.htm#increments。這項研究也表明“比較在希爾排序中是最主要的操作,而不是交換。”用這樣步長序列的希爾排序比插入排序要快,甚至在小數組中比快速排序堆排序還快,但是在涉及大量數據時希爾排序還是比快速排序慢。

另一個在大數組中表現優異的步長序列是(斐波那契數列除去0和1將剩餘的數以黃金分割比的兩倍的進行運算得到的數列):(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)[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)
輸入:1個長度為n的矩陣a,矩陣的編號從0到n - 1
整數inc從n / 2到1,每次循環inc變為inc / 2
	i從inc到n - 1,每次循環i變為i + 1
		將a[ i ]的值賦給temp
		j從i 到inc,每次循環j變為j - inc
			如果a[ j − inc ]大於temp,則將a[ j - inc ]的值賦給a[ j ]
			否則跳出j循環
		j循環结束
		將temp的值賦给a[ j ]
	i循環结束
inc循環结束

程式代碼[编辑]

C語言[编辑]

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++[编辑]

template<typename T>
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;
    }
}

Java[编辑]

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;
            }
        }
    }

JavaScript[编辑]

Array.prototype.shell_sort = function() {
	var gap, i, j;
	var temp;
	for (gap = this.length >> 1; gap > 0; gap >>= 1)
		for (i = gap; i < this.length; i++) {
			temp = this[i];
			for (j = i - gap; j >= 0 && this[j] > temp; j -= gap)
				this[j + gap] = this[j];
			this[j + gap] = temp;
		}
return this
};

Python[编辑]

def shell_sort(list):
    n = len(list)
    # 初始步長
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            # 每个步長進行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步長
        gap = gap // 2
    return list

PHP[编辑]

function shell_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
	for ($gap = count($arr)>>1; $gap > 0; $gap>>=1)
		for ($i = $gap; $i < count($arr); $i++) {
			$temp = $arr[$i];
			for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap)
				$arr[$j + $gap] = $arr[$j];
			$arr[$j + $gap] = $temp;
		}
}

Go[编辑]

package main

import (
	"fmt"
)

func ShellSort(array []int) {
	n := len(array)
	if n < 2 {
		return
	}
	key := n / 2
	for key > 0 {
		for i := key; i < n; i++ {
			j := i
			for j >= key && array[j] < array[j-key] {
				array[j], array[j-key] = array[j-key], array[j]
				j = j - key
			}
		}
		key = key / 2
	}
}

func main() {
	array := []int{
		55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9,
	}
	fmt.Println(array)
	ShellSort(array)
	fmt.Println(array)

}

引用[编辑]

  1. ^ Pratt, V. Shellsort and sorting networks (Outstanding dissertations in the computer sciences). Garland. 1979. ISBN 0-824- 04406-1.  (This was originally presented as the author's Ph.D. thesis, Stanford University, 1971)
  2. ^ A154393 The fibonacci to the power of two times the golden ratio gap sequence