计算机科学

首页 > 计算机科学

希尔排序

2018-08-28 09:41:55     所属分类:排序算法
希尔排序
Step-by-step visualisation of Shellsort
以23, 10, 4, 1的步长序列进行希尔排序。
分类 排序算法
数据结构 数组
最坏时间复杂度 根据步长序列的不同而不同。已知最好的:
最优时间复杂度 O(n)
平均时间复杂度 根据步长序列的不同而不同。
最坏空间复杂度 O(n)
希尔排序算法彩条

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

目录

  • 1 历史
  • 2 算法实现
  • 3 步长序列
  • 4 伪代码
  • 5 程序代码
    • 5.1 C语言
    • 5.2 C++
    • 5.3 Java
    • 5.4 JavaScript
    • 5.5 Python
    • 5.6 PHP
    • 5.7 Go
  • 6 引用

历史

希尔排序按其设计者希尔(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,...),该序列的项来自这两个算式1。这项研究也表明“比较在希尔排序中是最主要的操作,而不是交换。”用这样步长序列的希尔排序比插入排序要快,甚至在小数组中比快速排序和堆排序还快,但是在涉及大量数据时希尔排序还是比快速排序慢。

另一个在大数组中表现优异的步长序列是(斐波那契数列除去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 ← ai        
        j ← i        
        while j ≥ inc and aj − inc > temp do:            
            aj ← aj − inc            
            j ← j − inc        
        aj ← temp    
    inc ← round(inc / 2)
输入:1个阵列名称为a,1个长度名称为n,阵列的编號从0到n - 1
整数inc从n / 2到1每次迴圈inc变为inc / 2
	i从inc到n - 1每次迴圈i变为i + 1
		將ai的值丟到temp
		j从i - inc到0每次迴圈j变为j - inc
			如果aj大於temp则將aj + inc的值丟到aj
			否则跳出j迴圈
		j迴圈结束
		將temp的值丟到aj + inc
	i迴圈结束
inc迴圈结束

程序代码

C语言

void shell_sort(int arr, int len) {
	int gap, i, j;
	int temp;
	for (gap = len >> 1; gap > 0; gap = gap >>= 1)
		for (i = gap; i < len; i++) {
			temp = arri;
			for (j = i - gap; j >= 0 && arrj > temp; j -= gap)
				arrj + gap = arrj;
			arrj + 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 && arrayj < arrayj - h; j -= h) {
                std::swap(arrayj, arrayj - h);
            }
        }
        h = h / 3;
    }
}

Java

public static void shellSort(int array) {
    int number = array.length / 2;
    int i;
    int j;
    int temp;
    while (number >= 1) {
        for (i = number; i < array.length; i++) {
            temp = arrayi;
            j = i - number;
            while (j >= 0 && arrayj < temp) {
                arrayj + number = arrayj;
                j = j - number;
            }
            arrayj + number = temp;
        }
        number = number / 2;
    }
}

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 = thisi;
			for (j = i - gap; j >= 0 && thisj > temp; j -= gap)
				thisj + gap = thisj;
			thisj + gap = temp;
		}
};

Python

def shell_sort(list):
    n = len(list)
    # 初始步长
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            temp = listi
            j = i
            # 插入排序
            while j >= gap and listj - gap > temp:
                listj = listj - gap
                j -= gap
            listj = 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 && arrayj < arrayj-key {
				arrayj, arrayj-key = arrayj-key, arrayj
				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

上一篇:偏排序
下一篇:内省排序
相关推荐