【数据结构和算法】八大排序算法（插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序）
一、常见的排序算法
���入排序：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
选择排序：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
交换排序：
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
归并排序：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
二、排序算法详解
1.直接插入排序
基本思路
以升序为例：
- 单趟排序：将目标值(有序序列的后一个元素)插入到一个已经排好序的有序序列中
- 从有序序列的末尾倒着比较，如果目标值较小，就将该元素后移，并向前继续比较。
- 否则，就将目标值插入到该元素之后。
- 这里需要注意插入在序列中间和序列开头两种情况。
- 单趟拍完，有序序列的末尾向后扩张，继续下一趟排序，直到全部待排序的数据元素排完 。
void InsertSort(int *arr, int sz){
assert(arr != NULL);
//end的范围[0,sz-2]，给x留一个空间
for (int i = 0; i = 0)
{
if (x
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
- 动画演示：
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N) ~ O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
2.希尔排序
基本思路：
- 希尔排序是直接插入排序的优化版本：由于直接插入排序对顺序有序或接近有序的序列排序效率很高。所以希尔排序先通过多次分组预排序使序列接近有序，最后再进行直接插入排序≈O(N)，以此来提高效率。
- 多次分组预排序：就是将序列进行间隔分组，对同一组内的元素进行直接插入排序，并不断缩小分组间距。
- 如何分组：
- 通过增量gap对序列进行分组控制，gap是组内元素之间的间距，同时也是组数。
- gap初始化为n; 每次分组预排gap = gap/3+1；除3是进过多次试验得出的最佳缩小系数，加1是为了避免跳过最后一次直接插入排序。
- 直到gap==1进行最后一次直接插入排序使序列顺序有序。
投机取巧：希尔排序的写法其实就是将直接插入排序中的+1变成+gap，再加上对增量gap的控制。
特性总结：
-
希尔排序的时间复杂度平均为：O(N^1.3)
-
共进行logN次直接插入排序，其中：
- 开始时gap较大：组内元素数量较少，因此即便是最坏情况时间复杂度都大约为：O(N)；同时由于分组间隔较大，大数字会很快移动到数列后面，使数列逐渐接近有序；
- gap逐渐变小直到1：组内元素数量增多，但由于数列逐渐接近有序，因此时间复杂度也大约为：O(N)
因此希尔排序的时间复杂度大约为：O(N*logN)，做到了对直接插入排序的优化。
以升序为例：
void ShellSort(int *arr, int n){ assert(arr != NULL); //写法一（便于理解）：排完一组再排下一组 int gap = n; while (gap > 1) { //多次分组预排序，分组数量每次减少，直到1组排完。 gap = gap / 3 + 1;//加1，防止跳过gap == 1 //每次排序的起点 for (int i = 0; i = 0) { if (x 1) { gap = gap / 3 + 1; for (int i = 0; i = 0) { if (x希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取gap = gap/3+1，重复上述分组和排序的工作。当到达gap==1时，所有记录在统一组内排好序。
-
动画演示：
-
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时是直接插入排序，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。
-
希尔排序的时间复杂度：
- gap越大，预排越快，预排后越不接近有序。（大数字会很快移动到后面）
gap越小，预排越慢，预排后越接近有序
- 分组预排序的时间复杂度：
最好：N/gap*gap —> O(N)（每组大约N/gap个元素）
最坏：(1+2+3+…+N/gap)*gap; （gap越大，越接近N最坏情况越接近O(N)）
- 希尔排序的时间复杂度：
- gap = gap/2;
大约为N*log2 N（进行lon2 N次预排，每次复杂度接近O(N)）
- gap = gap/3+1;
大约为N*log3 N
- gap由大变小，开始时由于gap很大，时间复杂度都大约为O(N)。多次预排序使得数组越来越接近有序。虽然gap变小了，每次排序的复杂度也都大约为O(N)。
- 多次实验得出希尔排序的时间复杂度平均大约为O(N^1.3)
- gap = gap/2;
3.选择排序
基本思路
-
left和right记录区间的左端和右端；
-
不断遍历数组，经过一次遍历选出区间中的最大值和最小值；
-
然后将最小值换到左端，最大值换到右端；
-
++left; --right; 当left
注意：交换元素时如果先后交换的下标恰好相同需要做出调整。
void SelectSrot(int *arr, int n){ assert(arr != NULL); int begin = 0; int end = n-1; //begin,end向中间靠拢 while (begin在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
- 动画演示：
- 直接选择排序的特性总结：
- 选择排序思路简单好理解，但是对有序序列无反应，复杂度恒为O(N^2)。效率低，实际中很少使用。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
4.堆排序
基本思路：
-
要先写一个向下调整函数。
-
先调堆，向下调整建堆：
- 升序：调大堆
- 降序：调小堆
-
利用堆删除思想来进行排序：
-
记录堆尾下标end，同时end是删除堆尾元素后的size值；
-
交换堆顶(0)堆尾(end)元素——将最大值交换到序列尾。
-
向下调整，但此时的调整范围到end——恢复堆结构选出最大值
-
–end——进行下一轮选择交换。
void AdJustDown(int *arr, int sz, int root){ assert(arr != NULL); int parent = root; int child = parent * 2 + 1; while (child = 0; for (int i = (sz - 2) / 2; i >= 0; i--) { AdJustDown(arr, sz, i); } //类似与删除堆顶元素，将剩余元素向下调整 //排到最后一个元素不需要再排了，所以end > 0; for (int end = sz - 1; end > 0; end--) { Swap(&arr[0], &arr[end]); AdJustDown(arr, end, 0); } }堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
-
动画演示：
HeapSort
-
堆排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
5.冒泡排序
基本思路
- end记录冒泡的最终位置；
- 待排区间中的数据前后两两比较，交换，冒泡到end；
- 如果在一趟比较中没有发生交换则提前结束循环；
- –end，准备冒下一个泡。当end > 0时循环继续。
void BubbleSort(int *arr, int sz){ assert(arr != NULL); //将最大值换到最后 int end = sz - 1; //只剩最后一个元素不需再排 while (end > 0) { //优化冒泡排序，一轮冒泡未发生交换返回 bool exchange = false; for (int i = 1; i if (arr[i] arr[right] ? mid : right; return arr[tmp1] > arr[tmp2] ? tmp2 : tmp1; } int Partion1(int *arr, int left, int right){ //三数取中 -- 有序的情况每次二分，将最坏情况变成最好情况 int midi = GetMidIndex(arr, left, right); Swap(&arr[midi], &arr[left]); int keyi = left; while (left =" "
-
-
- gap越大，预排越快，预排后越不接近有序。（大数字会很快移动到后面）
-