【探索排序算法的魅力：优化、性能与实用技巧】（上）：https://developer.aliyun.com/article/1425253
2.3 交换排序
2.3.1基本思想
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排 序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2.3.2冒泡排序
冒泡排序是数据两两比较，将小的交换到前面，每趟排序将最大的排序到最后面，假设有n个数据，只用进行n-1趟排序，同时我们还要注意每趟排序的比较次数是不同的，第一轮，所有数据都要排序，就是n-1轮比较，第二轮比较的时候，最大的数据已经到了正确的位置，所以第二轮就只有n-2个数据比较。
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //冒泡排序 void BubbleSort(int* a, int n) { for (int i = 0; i < n - 1; i++)//比较的趟数 { for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); } } } }
上面的代码就是我们的冒泡排序，但是如果经过第一轮交换后，数据就已经有序了，但是我们的程序还在上面一轮一轮比较，这样效率较低，我们可以设置一个标志，如果经过一轮排序没有数据交换，那就说明数据已经有序了。
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //冒泡排序 void BubbleSort(int* a, int n) { for (int i = 0; i < n - 1 ; i++)//比较的趟数 { int flag = 1;//默认数据有序 for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); flag = 0;//数据无序 } } if (flag == 1) break; } }
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
2.3.2快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值key，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { //= 代表只剩下一个值 if (left >= right) return; // 按照基准值对array数组的 [left, right)区间中的元素进行划分 int div = PartSort(array, left, right); // 划分成功后以div为边界形成了左右两部分 [left, div-1) 和 [div+1, right) // 递归排[left, div-1) QuickSort(array, left, div-1); // 递归排[div+1, right) QuickSort(array, div + 1, right); }
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
单趟排序
//1. hoare版本 int PartSort(int* a, int left, int right) { int key = a[left]; while (left < right) { //右边找小 while (a[right] > key) { right--; } //左边找大 while (a[left] < key) { left++; } Swap(&a[left], &a[right]); } //key和相遇位置交换 Swap(&key, &a[left]); return left; }
我们看看上面的代码有问题没？我们来看看下面的图。
很明显，根据我们上面的代码，当key和a[left]、a[right]相等的时候，程序是不是就卡死啦。所以我们需要修改上面的循环条件key和a[left]、a[right]相等的时候，left和right的值都要改变。
//1. hoare版本 int PartSort(int* a, int left, int right) { int key = a[left]; while (left < right) { //右边找小 while (a[right] >= key) { right--; } //左边找大 while (a[left] <= key) { left++; } Swap(&a[left], &a[right]); } //key和相遇位置交换 Swap(&key, &a[left]); return left; }
我们再看看上面的代码还有问题没？我们来看看下面的图。
如果a[right]的值都大于key，那么right会一直减，最后就会越界的问题；同样a[left]的值都大于key，那么left会一直加，最后就会越界的问题。
//1. hoare版本 int PartSort(int* a, int left, int right) { int key = a[left]; while (left < right) { //右边找小 while (left < right && a[right] >= key) { right--; } //左边找大 while (left < right && a[left] <= key) { left++; } Swap(&a[left], &a[right]); } //key和相遇位置交换 Swap(&key, &a[left]); return left; }
我们再看看上面的代码还有问题没？我们来看看下面的图。
当最后right和left相遇的时候，此时执行Swap(&key, &a[left])，但是只是和key这个局部变量交换，并不是和数组里面的内容交换，数组里面的那个key值元素没有变化，我们可以通过下标去实现数组内容的交换。
//1. hoare版本 int PartSort(int* a, int left, int right) { int keyi = left; while (left < right) { //右边找小 while (left < right && a[right] >= a[keyi]) { right--; } //左边找大 while (left < right && a[left] <= a[keyi]) { left++; } Swap(&a[left], &a[right]); } //key和相遇位置交换 Swap(&a[keyi], &a[left]); return left; }
这里有一个疑问？为什么相遇的地方的值比key值一定小呢？怎么做到的呢？？？右边先走才能做到相遇的地方的值比key值一定小。
相遇情况：
- 如果左边先走，相遇位置是R的位置，L和R在上一轮交换过，交换后R的位置一定比key大，此时和key交换没有意义。
- 如果R先走找到比key小的值停下来了，然后L再走，找比key大的值，没有找到和R相遇了，相遇位置比key小，交换之后满足左边值比key小，右边比key大。
上面的hoare版本有很多的坑，下面我们来换一种写法：挖坑法
//挖坑法 int PartSort1(int* a,int left,int right) { int key = a[left];//保存key值，形成第一个坑位 int hole = left; while(left < right) { //右边先走，找小，填写到左边坑位，右边形成新的坑位 while(left < right && a[right] >= key) { right--; } a[hole] = a[right]; hole = right; //左边再走，找大,填写到右边坑位，左边形成新的坑位 while(left < right && a[left] <= key) { left++; } a[hole] = a[left]; hole = left; } //相遇的位置放key a[hole] = key; return hole; }
除了上面的这种写法，我们还有一张前后指针法。cur找小，找到之后让prev加加，再交换cur和prev处的值，prev在这里有两种情况，在cur还没遇到比key大的值得时候，此时prev紧跟cur，在cur遇到比key大的值的时候，prev在比key大的一组值得前面。本质是：把一段大于key的区间往右推，同时把小的甩到左边。
//前后指针版本 int PartSort(int* a,int left,int right) { int cur = left + 1; int prev = left; int keyi = left; while(cur < right + 1) { if(a[cur] < a[keyi] && cur != prev) { Swap(&a[cur],&a[++prev]); } cur++; } Swap(&a[keyi],&a[prev]); return prev; }
其实我们上面的三种快速排序遇到有一种情况就会对时间的消耗巨大，在利扣上运行就会出现超出时间限制的错误，什么情况呢？如果我们要排序的数是一组数据量极大的重复数字，此时的三数取中就没有任何意义，且上面三个版本的写法都不能处理这个问题，拿上面的hoare版本来说，如果是一组重复数据，hoare每次都是从右边先开始以此往左边找比keyi小的值，但是此时数组中的值都是一样的，找不到比keyi小的值，只能keyi就只能和right交换，我们想想，如果是一组数据重复极大的值，每次都要这样，消耗的时间是非常巨大的。因此这里可以使用第四种写法，三路划分：把小于key往左推，等于key换到中间，大于key的往右推。
三路划分：
- 1.cur小于key时，交换cur和left位置的值，然后再++cur，++left。
- 2.cur等于key时，直接++cur。
- 3.cur大于key时，交换cur和right位置的值，这里不能直接++cur，因为交换cur和right位置的值之后，此时不清楚cur位置与key位置值得大小关系，需要先--right，然后再比较cur位置与key位置值得大小关系。
结束条件：cur > right
【探索排序算法的魅力：优化、性能与实用技巧】（下）：https://developer.aliyun.com/article/1425264
