【21天算法挑战赛】排序算法——希尔排序

​
​💬💬作者有话想说：

💟作者简介：我目前是一个在校学生，想通过自己的学习努力让自己的技术、知识都慢慢提升，希望我们一起学习呀~💜💜💜
 
☂️兴趣领域：目前偏向于前端学习 💜💜💜
 
🎬> 活动地址：CSDN21天学习挑战赛
 
💜有话想说：写博客、记笔记并不是一种自我感动，把学到的东西记在脑子里才是最重要的，在这个过程中，不要浮躁，希望我们都可以越来越优秀！💜💜💜
 
🪀语言说明：代码实现我会用Python/C++~

​

一、希尔排序

1.1.希尔排序简介

希尔排序(shell 排序)，其实也是插入排序的一种，又称缩小增量排序。我们可以把全部元素分成几组，等距离的元素在一组，然后每组元素比较大小，进行换位置。然后继续缩小间距，直到间距为1时停止，此时已有序，是改进版的插入排序。

1.2.希尔排序思路

• 动图演示：

💡💡思路：

1. 将一组数据进行分组，我们可以用gap=length/2 缩小增量以gap = gap/2 进行缩小增量操作。等间距的数据分为一组
2. 然后每组数据进行比较，如果同一组前面的数大于后面的数，则换位置，否则不用交换，此时运用直接插入排序
3. 此时第一轮分组结束
4. 第二轮分组 gap = gap/2 同上步操作一样进行交换
5. 等到gap=1时结束，此时数据有序

1.3.时间复杂度

• 增量的变化会直接影响到希尔排序的性能，因此希尔排序的时间复杂度与增量序列高度相关
  这个时间复杂度 还不太理解。。。。。

1.4.空间复杂度

• 算法在执行过程中只需要定义的几个临时变量，所以空间复杂度为常数级：O(1)。

1.5.代码实现

C++代码：

#include 
using namespace std;
 
void shellSort(int arr[], int n)
{
	int tmp = 0;
	int gap = n / 2;
	while (gap)
	{
		for (int i = gap; i < n; i++)
		{
			tmp = arr[i];
			int j = i;
			// 直接插入排序
			while (j >= gap && tmp < arr[j - step])   
			{
				arr[j] = arr[j - gap];
				j -= gap;
			}
			arr[j] = tmp;
		}
 		// 缩短增量
		gap = gap / 2;
	}
}
 
int main()
{
	int arr[]{ 8, 13, 2, 44, 3, 7, 15, 4, 9, 10};
	int n = sizeof(arr) / sizeof(arr[0]);
	shellSort(arr, n);
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

Python代码:

def shell_sort(arr):
    n = len(arr)
    # 初始步长
    gap = n // 2
    # gap变化到0之前，插入排序执行的次数
    while gap > 0:
        # 按步长进行插入排序
        for j in range(gap, n):
            i = j
            # 插入排序
            while i > 0:
                if arr[i] < arr[i - gap]:
                    arr[i], arr[i - gap] = arr[i - gap], arr[i]
                    i -= gap
                else:
                    break
        # 缩短增量
        gap = gap // 2
 
if __name__ == "__main__":
    arr = [8, 13, 2, 44, 3, 7, 15, 4, 9, 10]
    shell_sort(arr)
    print(arr)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

1.6.优缺点

优点：

不需要大量的辅助空间，中等大小规模表现良好

缺点：

很不稳定！

希尔排序和插入排序

希尔排序利用了插入排序对“部分有序”或“小规模”数组高效排序的优势：分组是为了让插入排序每次处理小规模数组；经过多次分组排序后整个数组变得“部分有序”，最后再用一次插入排序。​

• 希尔排序特性

1. 当数组长度很大时，使用插入排序有个弊端，就是如果最小值排在很末端的时候，插入排序需要从末端开始，逐个往前比较到第一个位置，很低效。而希尔排序通过分组的方式，直接让前端跟末端的元素进行比较，解决了插入排序的这个弊端。
2. 在希尔排序中，一个数组在进行了n-排序之后，再进行更细化的k-排序，这个数组仍然是满足n-排序的，所以这个数组是越来越有序。
3. 当一开始增量gap 很大的时候，每一个子数组的元素很少，所以对每个子数组用插入排序进行内部排序是很高效的；而后随着增量gap不断减小，这个数组是越来越有序的，此时使用插入排序也是很有利的。

• 综上，希尔排序会比插入排序更快，而且数组的大小越大，提升越明显。​