《排序算法总结》

引言：

编程学到现在，我们已经接触了很多种排序算法，这篇文章我就对常见的几种排序算法进行一个小结。

一： 排序算法分类：

二： 插入排序：

直接插入排序：

1. 概念：

直接插入排序是⼀种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
具体步骤：
当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时
用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较，找到插入位置
即将 array[i] 插入，原来位置上的元素顺序后移。

插入排序其实和我们打扑克牌很像。

2. 画图理解：

3. 动画理解：

4. 代码实现：

5. 测试：

6. 时空复杂度分析：

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

希尔排序：

1. 概念：

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数（通常是gap=n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。

2. 画图理解：

3. 代码实现：

注：

1. 第一层的while循环时当gap大于1时才一直进行分组，因为gap为1的时候就是直接插入排序了。
2. 第二层的for循环中写成 i < n - gap ，是因为最后一个元素是n - 1，当i 最后走到n - gap - 1 时 tmp 走到 n - 1 位置，正好不越界。
   希尔排序的特性总结
3. 希尔排序是对直接插入排序的优化。
4. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
   解释：
   在预处理之后，较小的数据会集中在前面，较大的数据会集中在后面，这样的话数据移动的次数就少了，因此时间复杂度就降低了。

4. 测试：

5. 时空复杂度分析：

三： 选择排序

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

直接选择排序：

1. 概念：

1. 在元素集合 array[i]--array[n-1] 中选择关键码最大(小)的数据元素。
2. 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换。
3. 在剩余的 array[i]--array[n-2]（array[i+1]--array[n-1]） 集合中，重复上述步骤，直到集合剩余 1个元素。

2. 动画理解：

3. 代码实现：

4. 测试：

时空复杂度分析：

1. 直接选择排序 非常好理解，但是效率不是很好，实际中很少使用。
2. 时间复杂度：O(N )
3. 空间复杂度：O(1)

堆排序：

1. 概念：

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据，需要注意的是排升序要建大堆，排降序建小堆。
在二叉树那一篇博客中我们已经实现过堆排序，这里不再赘述。
具体可参考我这篇博客： 《数据结构之美–二叉树》

四： 交换排序

交换排序基本思想：
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序

1. 概念：

前面在C语言阶段其实我们已经接触过冒泡排序了，冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡⼀样，根据自身大小一点一点向数组的一侧移动。

2. 动画理解：

3. 代码实现：

4. 测试：

5. 时空复杂度分析：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

快速排序

1. 概念：

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

2. 画图理解:

上面是快速排序的过程，不断拿基准值划分两块区间，一直到只剩一个元素，那么这个区间自己就是有序的，主要就是找基准值的操作，下面分为两种找基准值的方法：

3. 不同版本的快速排序：

（1）hoare版本

1. 创建左右指针，确定基准值。
2. 从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环。

画图分析：

注：这里当left和right相遇时，相遇点可能大于基准值，因此这时候不跳出循环。

代码实现：

测试：

（2）lomuto前后指针版本

基本思想：
创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

动图理解：

代码实现：

测试：

（3）非递归版本的快速排序：

非递归版本的快速排序需要借助数据结构：栈

画图分析：

代码实现：

测试：

4. 时空复杂度分析：

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(logn)

五：归并排序

归并排序：

1. 概念：

归并排序算法思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（DivideandConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序核心步骤：

归并排序的核心操作就是合并两个有序数组

2. 代码实现：

3. 测试：

4. 时间复杂度分析：

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(n)

六：各种排序算法性能测试：

运行结果：

七：非比较排序

计数排序：

1. 概念：

计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

2. 图画理解：

但这里我们需要考虑一个问题：怎么来开count数组的大小呢？

综上所述：按照范围来开空间能尽可能地减少空间的浪费，因此我们采取按照范围来开数组的方式。

3. 代码实现：

4. 测试：

八：小结

完结撒花！！！