当前位置：网站首页>深度剖析“八大排序”（上）_ 探寻一些不为人知的细节

深度剖析“八大排序”（上）_ 探寻一些不为人知的细节

2022-08-10 07:56:00 【Dream_Y.Ocean】

前情提要

本章节是数据结构的八大排序（一）的相关知识~

接下来我们即将进入一个全新的空间，对代码有一个全新的视角~

以下的内容一定会让你对数据结构有一个颠覆性的认识哦！！！

以下内容以C语言的方式实现，对于数据结构来说最重要的是思想哦

以下内容干货满满，跟上步伐吧~

作者介绍：

作者： 热爱编程不起眼的小人物
作者的Gitee：代码仓库
系列文章&专栏推荐：《刷题特辑》、《C语言学习专栏》、《数据结构_初阶》
我和大家一样都是初次踏入这个美妙的“元”宇宙希望在输出知识的同时，也能与大家共同进步、无限进步

导航小助手
本章重点
一.插入排序
Ⅰ.直接插入排序
Ⅱ.希尔排序（缩小量排序）
🥯Ⅲ.总结
二.选择排序
Ⅰ.直接选择排序
Ⅱ.堆排序
🥯Ⅲ.总结
🫓总结

本章重点

深入了解与实现插入排序
深入了解与实现选择排序

一.插入排序

基本思想：

把待排序的记录按其关键码值的大小，逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

简单来说：

就是类似于打扑克牌面对待排序的牌组一样，将牌组的一端作为排序的开端【即上述的有序序列】，然后将剩下的牌【即待排元素】不断一个一个地往有序序列中插入到应有的位置上去

而对于插入排序类型最常见的有两种排序算法：

1️⃣直接插入排序
2️⃣希尔排序

接下来就让我们来深入了解这两种排序算法吧~

Ⅰ.直接插入排序

算法思想：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序
此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较
找到插入位置即将array[i]插入，原来位置上的元素顺序后移

️算法拆分：

假定有一个待排序数组：⌈3 2 6 8 4 1 9⌋，排升序

1️⃣将左边第一个元素⌈3⌋作为有序区间的起点
2️⃣即此时原数组中看似被分为两类数组：
- 有序区间：此时区间中有一个元素⌈3⌋
- 待排区间：区间中元素为⌈2 6 8 4 1 9⌋
3️⃣将待排区间中的第一个元素经过与有序区间中的元素比较后，插入到有序区间中合适的位置上去【依旧保持有序区间有序】
- 有序区间：此时区间中的元素为⌈2 3⌋
- 待排区间：区间中元素为⌈6 8 4 1 9⌋
4️⃣重复上述步骤，直至数组完全排序即可

特别注意：

上述算法拆分中看似是在操作两个区间，但实际上一直都是在原数组中进行排序【只是逻辑上将原数组分为两个区间去操作而已】
之所以每一次都用待排数组中的第一个元素去排序【即有序区间的下一个元素】，是因为这样子可以更加方便在原数组中挪动位置进行插入排序
- 不然如果每次都拿最后一个数据去插入排序的话，每次进行比较和插入排序都需要将整个数组都往后挪动一次【挪动次数相比较下更多，时间复杂度也随之上升】

动图示例：

代码实现：

void InsertSort(int*a, int n)
{
    
	//多趟
	for (int i = 0; i < n - 1; i++)
	{
    
		int end = i;
		//即 最后的情况是 0 - n-2都是有序区间，现在将 第 n-1 个元素 放进来排序

		int tmp = a[end+1]; //拿end的后一个位置的元素往前插

		while (end >= 0)
		{
    
			if (tmp < a[end])
			{
    
				a[end + 1] = a[end];
				end--;
			}
			else
			{
    
				//此时就放到end指向的位置的后面
				//1.要么一进来直接放
				//2.已经挪动的情况下，
				//end指向的后面是专门给tmp挪出来 放的
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

Ⅱ.希尔排序（缩小量排序）

算法思想：

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行插入排序
然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序

算法拆分：

希尔排序的本质：预排序直接插入排序
- 预排序：本质也是插入排序
  - 是对每一小组中的数据进行插入排序
  - 目的：让整个数组接近有序，使得一开始无序的数组趋向于让大的数往后面走，小的数往前面走
- 直接插入排序：在经过预排序使得整个数组接近有序后，就可以更加快速【中间也减少了数据的挪动次数】的将数组进行排序完全

️深入理解预排序：

待排数组为：⌈9 1 2 5 7 4 8 6 3 5⌋，排升序

1️⃣将数组间隔为gap的数据分为一组（假定gap为3，就会分为gap组）
2️⃣每组内的数据进行插入排序
- 即分⌈9 5 8 5⌋、⌈1 7 6⌋、⌈2 4 3⌋这三组
- 一次预排序的动图演示：
- 一趟下来后，数组内为：⌈5 1 2 5 6 3 8 7 4 9⌋，可见比一开始的顺序更加接近有序

综上：

我们可以发现预排序：

gap越大：
- 大的和小的数字可以更快挪动到对应的地方去
- 但越不接近有序
gap越小：
- 大的和小的数字可以更慢挪动到对应的地方去
- 但越接近有序
gap == 1：
- 本质就是直接插入排序

代码实现：

void ShellSort(int*a, int n)
{
    
	// gap > 1的时候，预排序
	// gap == 1的时候，直接插入排序
	int gap = n;

	while (gap > 1)
	{
    
		//控制gap的核心：
		gap = (gap / 3) + 1;

		for (int i = 0; i < n - gap; i++)
		{
    
			int end = i;
			int tmp = a[end + gap];

			while (end >= 0)
			{
    
				if (tmp < a[end])
				{
    
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
    
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

希尔排序的核心：

gap = (gap / 3) + 1;

gap > 1：预排序
gap == 1：直接插入排序
- 在gap <= 3的时候，+1就可以保证最后一次的gap必然是1
- 而且不一定/3，可以是任意选择
通过控制gap从而达到预排序直接插入排序效果

🥯Ⅲ.总结

排序特性：

1️⃣直接插入排序：

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度： $O（N^2）$
空间复杂度： $O （ 1 ）$
稳定性：稳定

2️⃣希尔排序：

希尔排序是对直接插入排序的优化【因为直接插入排序一开始的排序环境是很恶劣的，但希尔排序最后是在接近有序的环境下进行排序，所以环境更优】：
- 当gap > 1时都是预排序，目的是让数组更接近于有序
- 当gap == 1时，数组已经接近有序的了，这样就会很快
- 这样整体而言，可以达到优化的效果
时间复杂度【平均值】： $O（N^{1.3}）$ 【也可近似看为 $O （ N ）$ 】
【因为希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定】
空间复杂度： $O （ 1 ）$
稳定性：不稳定

️以上就是插入排序的相关内容啦，相信大家对插入排序有不一样的看法了吧🧡

二.选择排序

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

简单来说：

每次从待排序区间中遍历，选出最大值（或最小值）
将最大值（或最小值）根据排的顺序（升序or降序）放到相应的位置上去
重复上述操作直至完全排序

而对于选择排序类型最常见的有两种排序算法：

1️⃣直接选择排序
2️⃣堆排序

接下来就让我们来深入了解这两种排序算法吧~

Ⅰ.直接选择排序

算法思想：

与选择排序的大致思想基本相同，但有优化方案

️算法优化：

每次从待排序区间中遍历，选出最大值与最小值
将最大值与最小值根据排的顺序（升序or降序）放到相应的位置上去
重复上述操作直至完全排序

特别注意：

上述的算法优化相比于单次选取一个值进行排序，可一次性选取2个最值
但时间复杂度依旧没有发生变化，仍然是： $O（N^2）$
最小值交换的时候可能会对下一步的最大值交换产生影响：
- 即因为我们寻找最大值与最小值时，记录的是对应的下标
- 所以会有时候产生最小值所交换的位置恰好与最大值所在的位置相撞【即最大值所在的位置与待排区间的左边界重合】
- 那此时如果先交换最小值，那就会把一开始最大值 所在位置的值给交换走【即原本最大值的下标指向的就是最大值的位置，但因为最小值交换后，导致此时最大值下标指向的并不是真正的最大值】
所以遇见这种情况，我们一般在两次交换的中间加一个修正的情况，预防上述问题的发生

动图示例：

代码实现：

void Swap(int*p1, int*p2)
{
    
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int*a, int n)
{
    
	int left = 0;
	int right = n - 1;
	
	// 奇数个的时候，还剩下一个，但不需要排，就放在那里即可
	while (left < right)
	{
    
		int minIndex = left;
		int maxIndex = left;

		//选出了 最大值和最小值 的 下标
		for (int i = left; i <= right; i++)
		{
    
			if (a[i] < a[minIndex])
			{
    
				minIndex = i;
			}
			if (a[i] > a[maxIndex])
			{
    
				maxIndex = i;
			}
		}

		//把最小的换到左边
		Swap(&a[left], &a[minIndex]);
		
		//即 要修正 max的位置
		if (left == maxIndex)
		{
    
			maxIndex = minIndex;
		}
		
		//把最大的换到右边
		Swap(&a[right], &a[maxIndex]);
		
		left++;
		right--;
	}
}