数据结构八大排序算法



目录

前言

常见排序算法的实现

1.插入排序

2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序

6.快速排序

6.1 hoare版本

6.2挖坑法

6.3前后指针法

6.4快速排序优化

6.5快速排序非递归实现

7.归并排序

7.1递归实现

7.2非递归实现

8.计数排序(了解)

排序算法复杂度及稳定性分析

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

生活中各种地方都需要用到排序，所以学好排序算法是非常重要的。

排序分为 内部排序 和 外部排序。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

这部分主要是内部排序。排序讲解都以升序为例。

常见的排序算法：

思想：

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

实际中我们玩扑克牌时，就用了插入排序的思想：

演示过程动图：

单趟：若数组(arr)除最后一个元素外其余全部有序，设最后一个元素的下标为i，将arr[i]与前面的元素比较，前面的元素比他大则前面的元素向右移动，比他小则在该元素的后面插入。

复合：因为不知道数组中得到前几个元素是已经有序的，所以直接从第二个元素开始执行插入排序，单个过程与上述相同，将每个元素都进行一次插入排序。

代码如下：

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

希尔排序法又称缩小增量法。

基本思想：

先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。

然后将gap逐渐减小重复上述分组和排序的工作。

静态图演示：

动图演示： 

这里重要的是理解分组思想，每一个组其实就是一个插入排序，相当于进行多次插入排序。

代码如下：

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，这里不深究。
4. 时间复杂度O(N^1.5)
5. 空间复杂度O(1)
6. 稳定性：不稳定。

基本思想：

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，

然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，

重复这样的步骤直到全部待排序的数据元素排完 。

动图演示：

代码入下：

这里我们可以进行一个优化，最小值和最大值同时选，然后将最小值与起始位置交换，将最大值与末尾位置交换。

注意：

在进行最小值和最大值同时交换时也会出现一个问题，

如果最大值在起始位置的时候，交换了最小值之后，最大值就被交换到了min的位置，

如果继续交换max，就会将最小值交换到末尾位置。

所以，在每次交换了最小值之后应该判断一下最大值是否在起始位置，如果在需要将max赋值为min。

 直接选择排序的特性总结：

1.  直接选择排序思考非常好理解，但是效率不是很好(不论数组是否有序都会执行原步骤)。实际中很少使用
2.  时间复杂度：O(N^2)
3.  空间复杂度：O(1)
4.  稳定性：不稳定

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

• 升序：建大堆
• 降序：建小堆

2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

这里以升序为例：

• 首先应该建一个大堆，不能直接使用堆来实现。可以将需要排序的数组看作是一个堆，但需要将数组结构变成堆。
• 我们可以从堆从下往上的第二行最右边开始依次向下调整直到调整到堆顶，这样就可以将数组调整成一个堆，且如果建立的是大堆，堆顶元素为最大值。
• 然后按照堆删的思想将堆顶和堆底的数据交换，但不同的是这里不删除最后一个元素。
• 这样最大元素就在最后一个位置，然后从堆顶向下调整到倒数第二个元素，这样次大的元素就在堆顶，重复上述步骤直到只剩堆顶时停止。
   

动图演示：

注意：实际中并没有删除堆中元素，图中为了方便表示，将交换后的位置画成了空。

代码如下：

直接选择排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

冒泡排序应该是我们最熟悉的排序了，在C语言阶段我们就学习了冒泡排序。

他的思想也非常简单：

两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置。这是第一趟

一共进行n-1趟这样的交换将可以把所有的元素排好。

(n-1趟是因为只剩两个元素时只需要一趟就可以完成)

动图演示：

代码如下：

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

这里是排序算法的重点了，非常重要！

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，

其基本思想为：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
 

6.1 hoare版本

具体思路是：

1. 选定一个基准值，最好选定最左边或者最右边，选中间会给自己找麻烦。
2. 确定两个指针left 和right 分别从左边和右边向中间遍历数组。
3. 如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。
4. 然后右边的指针再走，遇到小于基准值的数就停下来。
5. 交换left和right指针对应位置的值。
6. 重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。

这样基准值左边的所有数都比他小，而他右边的数都比他大，从而他所在的位置就是排序后的正确位置。

之后再递归排以基准值为界限的左右两个区间中的数，当区间中没有元素时，排序完成。

动图演示：

这里选定基准值为最右边的元素。

单趟图解：

 继续按照上述步骤进行。。。

代码如下：

6.2挖坑法

挖坑法与上面的方法类似。

具体思路是：

1. 先将选定的基准值(最左边)直接取出，然后留下一个坑， 
2. 当右指针遇到小于基准值的数时，直接将该值放入坑中，而右指针指向的位置形成新的坑位，
3. 然后左指针遇到大于基准值的数时，将该值放入坑中，左指针指向的位置形成坑位，
4. 重复该步骤，直到左右指针相等。最后将基准值放入坑位之中。

之后也是以基准值为界限，递归排序基准值左右区间。 

动图演示：

这里不再单趟演示该过程。。。

代码如下：

6.3前后指针法

前后指针法是一个新思路，不太好理解，但是代码比较简单。

具体思路是：

1. 选定基准值，定义prev和cur指针(cur = prev + 1)
2. cur先走，遇到小于基准值的数停下，然后将prev向后移动一个位置
3. 将prev对应值与cur对应值交换
4. 重复上面的步骤，直到cur走出数组范围
5. 最后将基准值与prev对应位置交换
6. 递归排序以基准值为界限的左右区间

动图演示： 

 单趟演示：

代码如下： 

6.4快速排序优化

上面就是快速排序递归的三种方法。

但是上面的程序还有一些缺陷：

在基准值的选择上，如果选择的基准值为恰好为最小值，会进行不必要的递归。

在排序大量有序数据或者接近有序数据时，效率会比较低，甚至可能会出现程序崩溃的情况。

这是因为在排序有序数据时，快速排序的递归调用次数过多，会导致栈溢出的情况。

为了解决这些问题，这里有两种优化方法：

1. 三数取中法选基准值
2. 递归到小的子区间时，可以考虑使用插入排序

1.即在在起始位置，中间位置，末尾位置中选出中间值，作为基准值。

 2.类似于二叉树，每个子树都会进行一次递归调用，越到下面递归调用会越多。为了减少递归调用，当到递归到下层时，我们可以使用其他的排序来替代。这里我们使用插入排序。

以前后指针法为例，完整代码为：

6.5快速排序非递归实现

快速排序非递归实现，需要借助栈，栈中存放的是需要排序的左右区间。

而且非递归可以彻底解决栈溢出的问题。

其实他的思想与递归是类似的：

具体思想：

1. 将数组左右下标入栈，
2. 若栈不为空，两次取出栈顶元素，分别为闭区间的左右界限
3. 将区间中的元素按照前后指针法排序(其余两种也可)得到基准值的位置
4. 再以基准值为界限，若基准值左右区间中有元素，则将区间入栈
5. 重复上述步骤直到栈为空

代码如下： 

快速排序的特性总结：

1.  快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2.  时间复杂度：O(N*logN)
3.  空间复杂度：O(logN)
4.  稳定性：不稳定

7.1递归实现

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。  

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

归并排序核心步骤：

按照其算法思想：

首先应在数组中找出有序的序列，但数组是否有序编译器可不知道。

所以可以将数组划分，一分二，二分四......直到每个序列中只有一个数字。

一个数字总可以认为他是有序的吧。

最后将同时划分的序列合并。

动图演示：

代码如下：

7.2非递归实现

非递归实现的思想与递归实现的思想是类似的。

不同的是，这里的序列划分过程和递归是相反的，不是一次一分为二，而是先1个元素一组，再2个元素一组，4个元素一组....直到将所有的元素归并完。

静态图示：

代码如下：

归并排序的特性总结：

1.  归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2.  时间复杂度：O(N*logN)
3.  空间复杂度：O(N)
4.  稳定性：稳定

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
 

动图演示：

 代码如下：

注意：计数排序在排负数时，可将负数的类型转化成 unsigned int。

数组中元素有正有负的情况时不适用计数排序。 

计数排序的特性总结：

1.  计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2.  时间复杂度：O(MAX(N,范围))
3.  空间复杂度：O(范围)
4. 稳定性：稳定 

注：在特殊情况下，排序的时间复杂度会发生变化，不能作为判断该排序是否稳定的依据。

稳定性：指数组中相同元素在排序后相对位置不发生变化。

最后我们对各种排序算法进行一个简单的测试：随机测试10000个数据

如有错误，感谢指正~

来都来了，点个赞再走吧~~

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/9650.html