【数据结构】排序算法---希尔排序

文章目录

• 1. 定义
• 2. 算法步骤
• 3. 动图演示
• 4. 性质
• 5. 算法分析
• 6. 代码实现
• 结语

1. 定义

希尔排序（英语：Shell sort），也称为缩小增量排序法，是[直接插入排序]的一种改进版本。希尔排序以它的发明者希尔（英语：Donald Shell）命名。是第一个突破 O ( n 2 ) O(n^2) O(n2)的排序算法，它与插入排序的不同之处在于，它会优先比较距离较远的元素。

2. 算法步骤

排序对不相邻的记录进行比较和移动：

1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
2. 对这些子序列进行插入排序；
3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为1。

3. 动图演示

基本思想：先选定一个整数（通常是 g a p = n / 3 + 1 gap = n/3+1 gap=n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后 g a p = g a p / 3 + 1 gap=gap/3+1 gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当 g a p = 1 gap=1 gap=1时，就相当于直接插入排序。

它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接入排序算法的。

4. 性质

稳定性：

希尔排序是一种不稳定的排序算法。

空间复杂度：

希尔排序的空间复杂度为 O ( 1 ) O(1) O(1)。

时间复杂度：

希尔排序的最优时间复杂度为 O ( n ) O(n) O(n)。

希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取有关。设间距序列为 H H H，有 H H H的两种经典选取方式，这两种选取方式均使得排序算法的复杂度降为级别 O ( n 2 ) O(n^2) O(n2)。

希尔排序的平均时间复杂度可以降为 O ( n 1.3 ) O(n^{1.3}) O(n1.3)。

希尔排序时间复杂度不好计算，因为gap的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语言版)》— 严蔚敏书中给出的时间复杂度为：

5. 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

6. 代码实现

C语言

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//推荐写法：除3
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

Python

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

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

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

Go

func shellSort(arr []int) []int {
        length := len(arr)
        gap := 1
        for gap < length/3 {
                gap = gap*3 + 1
        }
        for gap > 0 {
                for i := gap; i < length; i++ {
                        temp := arr[i]
                        j := i - gap
                        for j >= 0 && arr[j] > temp {
                                arr[j+gap] = arr[j]
                                j -= gap
                        }
                        arr[j+gap] = temp
                }
                gap = gap / 3
        }
        return arr
}

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！