数据结构-十大排序算法集合（四万字精讲集合）

作者：盐析白兔 | 2024-07-19 03:34:25

踩

个人主页：Jason_from_China-CSDN博客

所属栏目：数据结构系统性学习_Jason_from_China的博客-CSDN博客

前言

1，数据结构排序篇章是一个大的工程，这里是一个总结篇章，配备动图和过程详解，从难到易逐步解析。

2，这里我们详细分析几个具备教学意义和实际使用意义的排序：

冒泡排序，选择排序，插入排序，希尔排序，快排（递归，霍尔版本），快排（递归，前后指针版本），快排（非递归版本），堆排序（解决top_k问题），归并排序（递归），归并排序（非递归），计数排序

3，这里我想说一下，学习排序之前需要了解一些相关的知识，

复杂度：目的是了解算法的时间复杂度，复杂度精讲（时间+空间）-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138073981
栈和队列：目的是在排序非递归实现里面，我们需要用到栈，比如速排的非递归实现，数据结构-栈和队列(速通版本)-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138715165
二叉树：目的是在排序计算里面，递归的解决方式是比较常用的方式，二叉树正好是用递归来完成的，可以辅助我们深入的了解一下排序的递归数据结构-二叉树系统性学习（四万字精讲拿捏）-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138799868

4，当然最后一点就是这些知识也可以不直接涉及到，如果你的时间比较紧张的话，只是理解起来相对而言需要一点难度，这些知识不是必须的。需要知道的是，这些知识可以帮助你深入理解排序的逻辑。

5，对于排序的学习很重要的一点就是，每次实现的时候我们往往需要先实现单趟排序的实现，之后再实现多趟的完结，这个是很重要的思路

6，这里的代码观看，尤其是对于排序代码的实现

先看内循环，因为内循环是单趟实现
再看外循环，因为外循环是全部实现逻辑。
这里一定不能搞错顺序，不然数据结构排序篇章很容易就无法看懂。
并且单趟实现往往重于多趟实现，因为多趟实现往往是单趟循环的循环和重复

冒泡排序

前言

冒泡排序具备很强的教学意义，但是没有什么实践意义，这里作为第一个讲解的排序，目的是从简单开始讲解，方便理解

冒泡排序gif

冒泡排序单趟实现

冒泡排序一次只解决一个数字，交换一个数字之后，开始交换第二个数字

那么多趟实现就直接for循环多趟实现就可以了

冒泡排序多趟实现逻辑

举例2（无法理解可以先不看举例2，这里是参照组）：

假设初始数组： [4, 2, 9, 1, 5]
第一轮后： [2, 4, 9, 1, 5] (9移到末尾)
第二轮后： [2, 4, 1, 5, 9] (9和5移到末尾)
第三轮后： [2, 1, 4, 5, 9] (9、5和4移到末尾)
第四轮后： [1, 2, 4, 5, 9] (9、5、4和2移到末尾)
第五轮后： [1, 2, 4, 5, 9] (数组已经排序完成)

冒泡排序注意事项

单趟循环需要注意事项

这里如果传参如果传递是是n，那么单趟实现的时候，我们不能循环n次数，只能循环n-1次数，因为

多趟循环需要注意事项

冒泡排序的交换逻辑

冒泡排序代码实现
//交换函数
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] < a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
			}
		}
	}
}
解释：

交换函数（Swap）：

函数原型：void Swap(int* p1, int* p2)
参数：p1 和 p2 是指向两个整数的指针。
功能：交换两个指针所指向的整数的值。
实现：首先，使用一个临时变量 tmp 存储 p1 指向的值。然后将 p2 指向的值赋给 p1 指向的位置，最后将临时变量 tmp（原来 p1 的值）赋给 p2 指向的位置。

冒泡排序（BubbleSort）：

函数原型：void BubbleSort(int* a, int n)
参数：a 是指向整数数组的指针，n 是数组中元素的数量。
功能：对数组 a 进行原地排序，使数组中的元素按照非递减顺序排列。
实现：冒泡排序通过重复遍历要排序的数组，比较相邻元素，如果它们的顺序错误就把它们交换过来。遍历数组的工作是在外层循环中完成的，内层循环负责实际的比较和交换。
交换函数就是一个交换函数，因为后面我还需要调用，所以这里我单独拿出来。

冒泡排序时间复杂度计算

冒泡排序的时间复杂度计算基于算法执行的比较和交换操作的次数。下面是冒泡排序的时间复杂度分析：

最佳情况：当数组已经完全有序时，冒泡排序只需要进行一次遍历即可确定数组已经有序，不需要进行任何交换。在这种情况下，时间复杂度是 O(n)，其中 n 是数组的长度。

平均情况和最坏情况：在平均情况和最坏情况下，冒泡排序需要进行 n-1 次遍历，每次遍历中进行的比较次数依次减少。具体来说：

第一次遍历最多进行 n-1 次比较。
第二次遍历最多进行 n-2 次比较。
...
最后一次遍历进行 1 次比较。
总的比较次数可以表示为：(n-1) + (n-2) + ... + 1。这是一个等差数列求和问题，其和为 n(n-1)/2。因此，平均情况和最坏情况下的时间复杂度是 O(n^2)。

空间复杂度：冒泡排序是原地排序算法，它不需要额外的存储空间来创建另一个数组，只需要一个临时变量用于交换元素。因此，冒泡排序的空间复杂度是 O(1)。

稳定性：冒泡排序是稳定的排序算法，因为它不会改变相同元素之间的相对顺序。

总结来说，冒泡排序的时间复杂度是：

最佳情况：O(n)
平均情况：O(n^2)
最坏情况：O(n^2)

由于冒泡排序在大多数情况下效率不高，特别是对于大数据集，它通常不作为首选排序算法。然而，它的简单性和稳定性使其在某些特定情况下（如小数据集或基本有序的数据）仍然有用。

直接选择排序

前言

直接选择排序也是一个比较简单的排序，所以这里放在第二个进行讲解，这里和冒泡排序是有一点相似。直接选择排序和冒泡排序一样，也是具备一定的教学意义，但是没有什么实际操作的意义，因为直接选择排序的时间复杂度比较高，书写起来和插入排序又差不多，所以没有必要写直接选择排序。

直接选择排序gif

直接选择排序单趟实现

1，初始化min（最小值）=0（也就是最左边的下标）的元素为最小值

2，遍历数组，如果此时出现更小的元素，这个元素的下标是i，那么我们设定min=i

3，之后交换最左边的元素和数值最小元素，因为这个时候我们已经找到下标了

4，最后排序好的最小值放在了最左边，那么此时最左边所在位置不需要进行排序了，分离出来就可以

5，这里因为选择排序效率太低了，我们稍微进阶一下，我们从两侧开始，选出最小和最大，从而进行交换，虽然没有提高多少效率，但是还是比之前的速度快两倍

直接选择排序注意事项

1，这里begin和end都是外层循环，也就是随着++和--进行缩小差距

2，这里begin和end不是索引，而是缩小差距用的

3，这里是mini和maxi是索引

4，最后交换的时候交换的是下标的元素，不是下标

直接选择排序多趟实现图解

直接选择排序代码实现
//交换函数
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//直接选择排序
void SelectSort(int* a, int n)
{
	//多趟循环
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//单趟循环，找出最小值和最大值
		int mini = begin, maxi = end;
		for (int i = begin; i <= end; i++)
		{
			//找到最小值，赋值下标
			if (a[i] < a[mini])
			{
				mini = i;
			}
			//找到最小值，赋值下标
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		//把最小值和最大值放到开头和结尾去
		Swap(&a[mini], &a[begin]);
		Swap(&a[maxi], &a[end]);
		begin++; 
		end--;
	}
}
解释：

外层循环从索引0开始，直到倒数第二个元素。
在每次外层循环中，假设当前索引位置的元素是未排序部分的最小值。
内层循环从外层循环的下一个位置开始，遍历未排序部分的元素，寻找最小值的索引minIndex。
如果找到的最小值不在当前索引位置，使用Swap函数将其交换到当前索引位置。
这样，每次外层循环结束时，未排序部分的最小值都被移动到了排序好的部分的末尾。

注意：

直接选择排序不是稳定的排序算法，即相等元素之间的相对顺序可能会改变。
直接选择排序的时间复杂度是O(n^2)，在大多数情况下，它不如其他更高效的排序算法。
直接选择排序的空间复杂度是O(1)，因为它是原地排序算法。

选择排序时间复杂度计算

外层循环：选择排序算法有一个外层循环，它从第一个元素遍历到倒数第二个元素。这个循环执行了 n−1 次，其中 n 是数组的长度。

内层循环：对于外层循环的每一次迭代，都有一个内层循环，它从当前考虑的元素之后的第一个元素遍历到数组的最后一个元素。在第一次外层循环迭代时，内层循环执行 n−1 次；在第二次迭代时，执行n−2 次；依此类推，直到最后一次迭代，只执行一次。

总迭代次数：内层循环的总迭代次数可以表示为一个等差数列之和： (
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/849165