数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)（上）：https://developer.aliyun.com/article/1513566
3.交换排序
交换排序分为冒泡排序和快速排序，冒泡排序我们写过很多次了这里放个动图就不讲了。
3.1.1冒泡排序代码：
void BubbleSort(int* arr, int sz) { int i = 0; int j = 0; for (i = 0;i < sz - 1;i++) { int flag = 1; for (j = 0;j < sz - 1 - i;j++) { if (arr[j] > arr[j + 1]) { Swap(&arr[j], &arr[j + 1]); } flag = 0; } if (flag) { break; } } }
3.1.2 快速排序
3.1.2.1 Hoare法快速排序
Hoare法快速排序的思想
快速排序的单趟：key放到它正确的位置上(整体排完序后最终放的位置)，
key的左边的值比key小，key右边值比它大
单趟排完，再递归让key左边区间有序，key的右边区间有序，整体就有序了
我们先写出单趟排序PartSort(int* arr,int left,int right)；因为是递归式的二叉树结构。
1.先选出一个key，一般是最左边或者最右边的。（后面用三数取中选，现在先选最左）
2.定义left和right，left向右遍历序列，right向左遍历序列（如果定义最左边的那个元素为key,那么right先走，若定义最右边的那个元素为key，则left先走）。
3.在走的过程中，若R遇到小于key的数则停下，到L开始走，直到L遇到比key大的数时，L也停下，将下标为left，right的数据交换，直到L与R相撞，最后把它们相遇的位置和a[keyi]交换，返回L与R相遇的位置。
4.经过一次单趟排序，最终使得key左边的数据都小于key，右边的数据都大于key。
5.然后我们再将key的左序列和右序列再次进行这种单趟排序，每进行一次单趟排序就可以确定一个数据的排序位置，如此递归操作下去，直到最后左右序列只有一个数据或没有数据，则层层返回，此时序列就排好啦。
int PartSort1(int* arr, int left, int right)//Hoare法快速排序 { int keyi = left;//左边做key while (left < right) { //右边先走 找小 控制不要错开不要越界 while (left < right && arr[right] >= arr[keyi]) { right--; } //左边再走 找大 控制不要错开不要越界 while (left < right && arr[left] <= arr[keyi]) { left--; } Swap(&arr[left], &arr[right]); } Swap(&arr[left], &arr[keyi]);//交换相遇的地方和关键字的位置 return left;//返回关键字的位置 } void QuickSort(int* arr, int left, int right) { if (left >= right) { return; } int keyi = PartSort1(arr, left, right); QuickSort(arr, left, keyi - 1); QuickSort(arr, keyi + 1, right); }
为什么左边做key,要让右边先走?
结论:因为要保证相遇位置的值，比key小或者就是key的位置
①right先走，right停下来,left去遇到right
则相遇位置就是right停下里的位置，right停的位置就是比key要小的位置
②right先走，right没有找到比key要小的值，right去遇到了left
相遇位置要么是left上一轮停下里的位置（本来是大的，但交换变成小的了），
要么就是key的位置（第一次往左找就找不到）
3.1.2.2 挖坑法快速排序
挖坑法 只是比Hoare法 好理解一点，并没有实质的改变
1.利用优化后的选key逻辑：三数取中，（后面讲，现在先选最左）
选出key变量作为坑位，保存作为坑位的值（保存起来就可以覆盖了，就相当于坑位）。
2.定义一个L，一个R，L从左向右走，R从右向左走
（若在最左边挖坑，则R先走；若在最右边挖坑，则L先走）。
3.假设我们定义最左边为坑位，在R走的过程中，若R遇到小于key的数，则将这个数抛入坑位，
然后这个数原来的位置变成坑位，然后L向右走走，若遇到大于key的数则停下，将这个数抛入坑位，
这个数的位置又形成新的坑位，如此循环下去，直到最终L与R相遇，
最后再将key抛入最后形成的坑位。
4.经过一次单趟排序，也能使得key左边的数据都小于key，右边的数据都大于key。
5.然后也是跟Hoare法一样，key的左右子序列不断的进行单趟排序（递归），直到左右序列只有一个数据或者没有数据，便停止递归，层层返回。
/*3.假设我们定义最左边为坑位，在R走的过程中，若R遇到小于key的数，则将这个数抛入坑位， 然后这个数原来的位置变成坑位，然后L向右走走，若遇到大于key的数则停下，将这个数抛入坑位， 这个数的位置又形成新的坑位，如此循环下去，直到最终L与R相遇， 最后再将key抛入最后形成的坑位。*/ int PartSort2(int* arr, int left, int right)//挖坑法快速排序 { int pit = left; int keyi = pit; while (left < right) { while (left < right && arr[right] >= arr[keyi]) { right--; } arr[pit] = arr[right]; pit = right; while (left < right && arr[left] <= arr[keyi]) { left++; } arr[pit] = arr[left]; pit = left; } arr[pit] = arr[keyi]; return pit; } void QuickSort(int* arr, int left, int right) { if (left >= right) { return; } //int keyi = PartSort1(arr, left, right); int keyi = PartSort2(arr, left, right); QuickSort(arr, left, keyi - 1); QuickSort(arr, keyi + 1, right); }
3.1.2.3 前后指针法快速排序
前后指针法比前面两种方法更简洁,理解后不易错
1.用三数取中法，选出一个key（后面讲，这里先选最左边的）。
2.刚开始prev指向序列开头，cur指向prev+1的位置。
3.若cur指向的值比key小，则cur停下来，++prev，交换prev和cur位置上的数据，然后cur继续往后++，prev紧跟cur，但若cur指向的数据大于等于key，则cur继续++，但prev不动，如此规律进行下去，直到cur越界，跳出循环，最后将prev指向的数据和keyi指向的数据交换即可。
4.经过一次单趟排序，也能使得key左边的数据都小于key，右边的数据都大于key。
5.然后也是跟Hoare法一样，key的左右子序列不断的进行单趟排序（递归），直到左右序列只有一个数据或者没有数据，便停止递归，层层返回。
int PartSort3(int* arr, int left, int right)//前后指针法快速排序 { int prev = left; int cur = left + 1; int keyi = left; while (cur <= right) { /*while (cur <= right && arr[cur] >= arr[keyi]) { cur++; } if (cur <= right) { prev++; Swap(&arr[cur], &arr[prev]); cur++; }*/ if (arr[cur] < arr[keyi] && ++prev != cur)//反正都要cur++，注意这里prev已经++了 { Swap(&arr[cur], &arr[prev]); } cur++;//前面注释的优化 } Swap(&arr[prev], &arr[keyi]); return prev; } void QuickSort(int* arr, int left, int right) { if (left >= right) { return; } //int keyi = PartSort1(arr, left, right); //int keyi = PartSort2(arr, left, right); int keyi = PartSort3(arr, left, right); QuickSort(arr, left, keyi - 1); QuickSort(arr, keyi + 1, right); }
3.1.3 快速排序的两个优化
3.1.3.1 三数取中
快速排序的时间复杂度是O(NlogN)，是我们在理想情况下计算的结果。在理想情况下，
我们每次进行完单趟排序后，key的左序列与右序列的长度都相同：
若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，
那么快速排序的时间复杂度就是O(NlogN)。
可是谁能保证你每次选取的key都是正中间的那个数呢？当待排序列本就是一个
有序（或者接近有序）的序列时，我们若是依然每次都选取最左边或是最右边的数作为key，
那么快速排序的效率将达到最低
可以看到，这种情况下，快速排序的时间复杂度退化为O(N2)。其实，
对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则效率越高。
为了少出现上面的情况，有人提出随机选key,但还是会出现极端情况，
为了避免这种极端情况的发生，于是出现了三数取中：
三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。
三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。
这就确保了我们所选取的数不会是序列中的最大或是最小值了。
所以说加入三数取中后才认为快速排序的时间复杂度是O(NlogN)。
int GetMidIndex(int* arr, int left, int right) { int mid = left + (right - left) / 2; if (arr[mid] > arr[left]) { if (arr[mid] < arr[right]) return mid; else if (arr[left] > arr[right]) return left; else return right; } else { if (arr[mid] > arr[right]) return mid; else if (arr[left] > arr[right]) return right; else return left; } }
3.1.3.2 小区间优化
随着递归深度的增加，递归次数以每层2倍的速度增加，这对效率有着很大的影响。
为了减少最后几层递归，我们可以设置一个判断语句，
当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。
小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，
而且待排序列的长度越长，该效果越明显。
这时我们前面讲的对于小区间快速且简单的几个排序中的选择排序就派上用场（呼应铺垫）
虽然减少了80%以上的递归，但是现在编译器对递归的优化已经很大了，
所以小区间优化并没有三数取中对快排的优化大。
void QuickSort(int* arr, int left, int right) { if (left >= right) { return; } if (right - left + 1 < 19)//可以自己取，官方是十几 { InsertSort(arr + left, right - left + 1); } else { //int keyi = PartSort1(arr, left, right); //int keyi = PartSort2(arr, left, right); int keyi = PartSort3(arr, left, right); QuickSort(arr, left, keyi - 1); QuickSort(arr, keyi + 1, right); } }
3.1.4 快速排序非递归版
递归版的致命问题就是递归层次太深可能会导致栈溢出，因为栈是不大的
所以对应大多数递归我们都要掌握改非递归的能力。树的递归改非递归有点难，后面再学。
递归改非递归有两种方法
直接改循环。比如斐波那契数列，还有后面的归并排序
用数据结构的栈模拟递归，因为数据结构的栈是在堆申请空间的（以前写过），堆很大
递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。
一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。
非递归快排的基本思想：
1. 申请一个栈，存放排序数组的起始位置和终点位置。
2. 将整个数组的起始位置和终点位置入栈。
3. 由于栈的特性是：后进先出，right后进栈，所以right先出栈。
定义一个end接收栈顶元素，出栈操作、定义一个begin接收栈顶元素，出栈操作。
4. 对数组进行一次单趟排序，返回key关键值的下标。
5. 这时候需要排基准值key左边的序列。
如果只将基准值key左边序列的起始位置和终点位置存入栈中，等左边排序完将找不到后边的区间。
所以先将右边序列的起始位置和终点位置存入栈中，再将左边的起始位置和终点位置后存入栈中。
6.判断栈是否为空，若不为空 重复4、5步、若为空则排序完成。
这时我们把以前写的栈拷贝来：（后面会放完整八大排序和栈的代码）
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)_GR C的博客-CSDN博客
void QuickSortNonR(int* arr, int left, int right) { Stack st; StackInit(&st); StackPush(&st, right);//为了更类似上面的递归就先入右 StackPush(&st, left); while (!StackEmpty(&st)) { int begin = StackTop(&st); StackPop(&st); int end = StackTop(&st); StackPop(&st); int keyi = PartSort3(arr, begin, end); //区间被成两部分了 [begin,keyi-1] [keyi+1,end] if (keyi + 1 < end)//先处理右 { StackPush(&st, end); StackPush(&st, keyi + 1); } if(begin < keyi - 1) { StackPush(&st, keyi - 1); StackPush(&st, begin); } } StackDestroy(&st); }
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)（下）：https://developer.aliyun.com/article/1513609
