目录
- 一、交换排序
- 1.1 冒泡排序
- 1.2 快速排序
- 1.2.1 hoare法
- 1.2.2 挖坑法
- 1.2.3 前后指针法
- 1.3 快速排序优化
- 1.3.1 三数取中法选key
- 1.3.2 递归到小的子区间使用插入排序
- 1.4 快排非递归版
- 二、归并排序
- 2.1 归并排序
- 2.1.1 递归版
- 2.1.2 非递归版
一、交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
1.1 冒泡排序
说起冒泡排序，这也算是在我们学习编程时遇到的第一个排序算法，总体逻辑就是从待排序数组第一个一直向后遍历，遇到比自己大的就记录该值，遇到比自己小的就交换，直到到达待排序数组结尾，此时待排序数组长度--，依此逻辑每次都能将最大值移动到最后。直到待排序数组长度为0，此时数组已有序。
冒泡排序动态演示：
在实现代码时，还可以增加一个变量bool Exchange = true，如果一趟遍历下来，没有任何数据进行交换，则exchange不变，代表此时数组已有序，那么便直接结束排序(if(exchange == true) break;)；如果发生数据交换，则改变exchange值为false，那么排序任然继续下一趟。 代码如下：
//冒泡排序 void BubbleSort(int* a, int n) { //排序趟数 for(int i = 0; i a[j + 1]) { Swap(&a[j], &a[j + 1]) exchange = false; } } if(exchange == true) break; } }冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度： O(N^2)
- 空间复杂度： O(1)
- 稳定性： 稳定
1.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
那么具体是如何实现的呢？可以参考如下过程：
事实上整体逻辑就是二叉树的前序遍历，即先处理当前数组，取基准值，以基准值为标准划分左右两部分，然后递归基准值左部分([begin, div - 1])，最后在递归基准值右部分([div + 1, end])。 将begin >= end作为结束条件，说明当前已经递归到的部分的数据个数 if(begin = end) return; // 按照基准值对a数组的 [begin, end]区间中的元素进行划分 int div = partion(a, begin, end); // 划分成功后以div为边界形成了左右两部分 [begin, div - 1] 和 [div + 1, end] // 递归排[begin, div - 1] QuickSort(a, begin, div - 1); // 递归排[div + 1, end] QuickSort(a, div + 1, end); }
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，我们可以参照二叉树前序遍历（如有疑问请参考：【数据结构和算法】— 二叉树（3）–二叉树链式结构的实现（1））规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有：
1.2.1 hoare法
hoare法 动态演示：
hoare法主要思想：定义两个变量分别对应待排序数组首元素下标int left = begin，待排序数组尾元素下标int right = end。右边先向左找小于a[keyi]的值，找到后，左边在向右找大于a[keyi]的值，然后交换两数Swap(&a[left], &a[right])。需要注意的是，在寻找过程中要保证left
hoare法代码：
//hoare法 int partion(int* a, int begin, int end) { int left = begin, right = end; //设基准值为首元素，keyi记录下标 int keyi = begin; while(left相信看完上面上面代码和演示，会有这么一个问题：为什么相遇的位置比a[keyi]要小呢？
因为左边做keyi，右边right先走：
- 情况1：right先遇到left。此时right没有找到比a[keyi]小的，一直走，直到遇到left，相遇位置是a[left]，一定比a[keyi]小；
- 情况2：left先遇到right。因为是right先走，找到小于a[keyi]的元素便会停下，接着left找大，没有找到，遇到了right停下来了，相遇点是right，比a[keyi]要小。
当然如果右边做基准值，那么必须要左边left先走，才能确保相遇点都大于a[keyi]。
1.2.2 挖坑法
挖坑法 动态演示：
挖坑法主要思想：先取出基准值，并将其赋值给key ，此时这个位置就空出来了，称之为坑位，用holei来记录坑位的下标。 紧接着右边向左找小（即小于key的元素），若找到就将该元素填入坑位中a[holei] = a[end]，并改变坑位为替换元素的下标holei = end，然后左边向右找大（即大于key的元素），同样填入坑位，并更新坑位。依次循环，直到左右相遇begin == end，这时将基准值填入坑中(a[holei] = key)，并返回坑位return holei;。
挖坑法代码：
//挖坑法 int partion(int* a, int begin, int end) { //基准值记录 int key = a[begin]; //坑位记录 int holei = begin; while(begin = key) --end; a[holei] = a[end]; holei = end; //左边找小，填右坑，更新坑位 while(begin a[end]) return midi; else if(a[end] > a[bedin]) return begin; else return end; } } int midi = GetMidi(a, begin, end); Swap(&a[midi], &a[begin]);1.3.2 递归到小的子区间使用插入排序
为什么说递归到小的子区间要使用插入排序呢？ 根据这里写的递归的特性，可以看出整体的逻辑是一棵二叉树。说到二叉树，二叉树最后一层的节点数大约占整个二叉树的节点数的一半，这样一来时间复杂度便会升高。那么我们只需要想办法将最后两三层递归逻辑，使用其他效率高的排序给替换掉即可。 这样一来如果替换掉两层，就减少了大约75%的递归，替换三层,大约就减少了87.5%的递归。
小区间优化代码如下：
//小区间优化 void QuickSort(int* a, int begin, int end) { if(begin >= end) return; if(end - begin + 1 //end - begin + 1 int keyi = partion(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } } ST s; STInit(&s); //先进栈一对数据 STPush(&s, end); STPush(&s, begin); while(!STEmpty(&s)) { //出栈一对数据，为此次排序范围 int left = STTop(&s); STPop(&s); int right = STTop(&s); STPop(&s); int div = partion(a, begin, end); //div 右部分进栈 if(right div + 1) { STPush(&s, right); STPush(&s, div + 1); } //div 左部分进栈 if(left快速排序的特性总结：
-
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序；
-
时间复杂度： O(N*logN)
-
空间复杂度： O(logN)
-
稳定性： 不稳定
二、归并排序
2.1 归并排序
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
归并排序 动态演示：
2.1.1 递归版
递归版的归并排序，逻辑上与二叉树的后序遍历十分相似。可先找到待排序数组的中间那个数的下标int mid = (begin + end) / 2;，将左部分[begin, mid]作为左子树，右部分[mid + 1, end]作为右子树，继续递归，直到begin >= end（即当前元素个数小于等于一个）结束并返回，当左右部分递归完便开始合并。
此处合并即为两待排序数组[begin, mid]和[mid + 1, end]，向动态开辟的数组tmp中拷贝并排序。 至于合并的逻辑就十分简单，两待排序数组元素依次比较，小的拷贝进tmp，直到一方拷贝完begin1 > end1或begin2 > end2，然后直接拷贝未拷贝完的一方，最后再使用memcpy()函数将tmp中数据（此时tmp中元素已有序）拷回a中。
代码如下：
//递归版 归并排序 void _MergeSort(int* a, int begin, int end, int* tmp) { if(begin >= end) return; int mid = (begin + end) / 2; //[begin, mid] [mid + 1, end] _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); //归并 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; //将两个数组合并为一个，并排为升序 while(begin1 if(a[begin1] -
