初识数据结构：排序算法
◆博主名称：少司府
欢迎来到少司府的博客☆*: .｡. o(≧▽≦)o .｡.:*☆
⭐数据结构系列个人专栏：
初阶数据结构_少司府的博客-CSDN博客
⭐编程基础训练系列个人专栏：
编程基础50题_少司府的博客-CSDN博客
⭐名不显时心不朽，再挑灯火看文章
目录
一、排序的概念及其运用
1.1 排序的相关概念
1.2 排序的相关运用
1.3 常见的几种排序算法
二、常见排序算法的实现（升序）
2.1 冒泡排序
2.2 选择排序
2.3 堆排序
2.3.1 向下调整函数
2.3.2 堆排序
2.4 插入排序
2.5 希尔排序
2.6 快速排序
2.6.1 hoare 版本
2.6.2 前后指针版
2.7 归并排序
2.8 计数排序
三、排序的总结
3.1 稳定性介绍
3.2 总结
一、排序的概念及其运用
1.1 排序的相关概念
| 排序 | 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 |
| 内部排序 | 数据元素全部放在内存中的排序。 |
| 外部排序 | 数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。 |
1.2 排序的相关运用
排序算法在生活中无处不在，购物APP中商品的价格排行、国内各个高校的排名等等。
1.3 常见的几种排序算法
除此之外，我们列举了以下几种常见的排序算法。
其中，我们比较熟悉的就是冒泡排序了。
我们可以通过下面这个网站来查看各种排序的演示图：
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
二、常见排序算法的实现（升序）
2.1 冒泡排序
冒泡排序作为常见的排序算法，其核心不过是遍历，两两交换，将大的数字冒到后面去，其时间复杂度是O(n^2)，本身没有什么实践意义，但是具有教学意义，作为新生入门的排序刚刚好。
2.2 选择排序
和冒泡排序一样，直接选择排序也是时间复杂度为O(n^2)的排序算法，其本身也没有什么实践意义。
其核心是：遍历，找到最大元素的下标maxi，将它与最后一个元素交换（这样就把最大的排到了最后）。这里做了优化，同时走最大和最小，同时排出最大和最小，可以提升一点点效率。
2.3 堆排序
2.3.1 向下调整函数
堆排序的核心就是“建堆”和“排序”，因此，我们需要先写一个向下调整函数来实现建堆。
如图，while循环向下不断调整，若孩子比父亲大，则交换。
2.3.2 堆排序
堆排序的主要排序逻辑如图，先建大堆，取堆顶元素放到最后，在缩减范围之后，不断向下调整，将大的数放到后面，完成升序的排序逻辑。
其具体逻辑在上期中讲过，可点击这里：https://blog.csdn.net/CAO_070413/article/details/158386332?fromshare=blogdetail&sharetype=blogdetail&sharerId=158386332&sharerefer=PC&sharesource=CAO_070413&sharefrom=from_link
堆排序的时间复杂度是O(N*logN)。
2.4 插入排序
在观看源码之前我们先简单介绍一下直接插入排序。
直接插入排序是一种简单的排序算法，其主要逻辑是：默认前面是有序的数列，不断将后面的数插入到前面的数列之中。
我们玩扑克牌的时候也是用的插入排序的逻辑。
如图，while循环之前定义一个end指向有序数列的最后一个数，tmp保存end后一个数，也就是待插入的数。
升序排序的话，如果tmp比end指向的数小，就不断把有序的数字往后推，当找到第一个小于等于tmp的数字时，就把tmp插到它的后面。
插入排序的时间复杂度是O(N^2)。
2.5 希尔排序
希尔排序的底层是插入排序，可以理解为对插入排序的拓展，由于是希尔这位大佬提出来的，所以叫做希尔排序（ShellSort）。
希尔排序的核心思想是：先对待排序数组进行预排序，使其变得相对有序，最后再进行直接插入排序。
虽然有预排序，看起来步骤多了，但实际上它的效率却是大大提高了。
如图，可以看到，希尔排序的底层仍然是插入排序，只是插入排序是一个一个地挪动，而希尔排序是先将数列分为多组，每组内部进行插入排序（也就是预排序），以gap为单位进行挪动。
gap=gap/3+1一个是减少预排序的次数，另一个是让最后一次gap=1，这样最后一次就是直接插入排序了。
希尔排序的时间复杂度是O(N^1.3)。
2.6 快速排序
2.6.1 hoare 版本
我们在学C语言的时候应该有了解或者学习过qsort这个函数，这个函数的底层就是快速排序。
这里有个动图展示快速排序：https://gitee.com/bithange/113-issues/raw/master/24%E5%B9%B4-05%E6%9C%8827%E6%97%A5--%E6%8E%92%E5%BA%8F/%E5%8A%A8%E5%9B%BE/hoare.gif
如图，初识化key指向第一个数，L和R同时往两边走，R先走，R找到比key小的数字，L找到比key大的数字，并将这两个数交换，当L和R相遇的时候，其指向的数字是比key小的，将key和相遇位置交换，再对左右两边进行此操作（也就是递归）。
如图，该代码在原版本上加入了三数取中和小区间优化。
三数取中是找到left、right和mid的中间值下标，key指向中间值，如果数组已经有序，没有优化的化会让其退化为时间复杂度为O(N^2)的算法，递归深度增加导致栈溢出。
小区间优化是让最后几层不递归，直接用其他的算法逻辑，这样能大大减少递归次数，提高效率。
2.6.2 前后指针版
由于hoare版本要考虑的细节比较多，且不容易理解，后来又对快速排序做了优化，前后指针版更容易理解一些。
这是前后指针的动图：
https://gitee.com/bithange/113-issues/raw/master/24%E5%B9%B4-05%E6%9C%8827%E6%97%A5--%E6%8E%92%E5%BA%8F/%E5%8A%A8%E5%9B%BE/%E5%89%8D%E5%90%8E%E6%8C%87%E9%92%88.gif
如图，初始化prev指向起始位置，cur指向后一个位置。cur向后面移动，当arr[cur] < arr[keyi]的时候，交换prev和cur指向的值，prev++和cur++，不断将比arr[keyi]小的值放到左边，大的值放到右边。
如图，可以将单趟封装成一个子函数。
2.7 归并排序
归并排序采用分治的思想，其核心是将已经有序的数列合并，变成一个新的有序的数列。
如图，类似于二叉树的结构，我们把数列不断分为两组，若只有一个数，则认为已经有序了。
如图，归并排序也是需要封装一个子函数来处理排序逻辑。
与其他排序不同的是，归并排序需要额外开一个空间复杂度为O（N）的空间，begin1、end1，begin2、end2分别指向两组数列的首尾，不断递归使其有序。
把排好序的数列不断追加到tmp数列中。
最后再用memcpy把tmp拷贝到原数组去。
归并排序时间复杂度是O(N*logN)，空间复杂度是O(N)。
2.8 计数排序
与上述排序都不一样的是，计数排序是一种非比较排序。其核心思想：统计相同元素出现次数，并根据统计的结果将序列回收到原来的序列中。
如图，先找到最大值和最小值相差的范围，再开辟一个count的空间用于统计次数，最后通过数字出现的次数来对原数组进行排序。
其算法的时间复杂度是O(N+range)，空间复杂度是O(N)。
三、排序的总结
3.1 稳定性介绍
稳定性概念：相等的值在排序后其相对位置保持不变，则稳定性强。
3.2 总结
| 时间复杂度 | 空间复杂度 | 稳定性 | |
| 直接插入排序 | O(N^2) | O(1) | 强 |
| 希尔排序 | O(N^1.3) | O(1) | 弱 |
| 选择排序 | O(N^2) | O(1) | 弱 |
| 堆排序 | O(N*logN) | O(1) | 弱 |
| 冒泡排序 | O(N^2) | O(1) | 强 |
| 快速排序 | O(N*logN) | O(logN) | 弱 |
| 归并排序 | O(N*logN) | O(N) | 强 |
本期的分享就到这里，如果觉得博主的文章比较对胃口的话，可以点一个小小的关注~
您的三连是我持续更新的动力~