每日回顾：简单用C写 冒泡排序、快速排序

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

//冒泡排序
void BubbleSort(int* a, int n) {for (int i = 0; i < n - 1; i++) {	//冒泡 n-1 次bool flag = false;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {Swap(&a[j], &a[j + 1]);}flag = true;}if (!flag) {break;}}
}

时间复杂度

O(n^2)

空间复杂度

原地修改，O(1)

快速排序

快速排序（Quick Sort）是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer）：通过一个划分操作将数据分为独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再递归地对这两部分数据分别进行排序操作。

递归版本

递归版本一：hoare

大致思想：通过左右下标指针不断的寻找交换，每趟分割可以将 1 个 a[keyi] 归位；递归地分割、归位子序列即可

右下标指针 right 从右开始寻找小于 a[keyi] 的值，左下标指针 left 从左开始寻找大于 a[keyi] 的值；然后交换 a[left] 和 a[right]，继续寻找直到 left 和 right 相遇，将 a[keyi] 归位

//单趟分割区间
int PartSort_1(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]);}Swap(&a[left], &a[keyi]);return left;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素，或区间不存在if (begin >= end) {return;}//分割区间int midi = PartSort_1(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi+1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi + 1, end);}

递归版本二：挖坑法

大致思想：hoare法是大小交换，而挖坑法是找到小了立即交换到左边，找到大了立即交换到右边，hole（坑）的值由 key 保存，坑的位置随着值的交换而变化

//单趟分割区间
//挖坑法
int PartSort_2(int* a, int left, int right) {int key = a[left];	//保存被挖坑的值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;}a[hole] = key;return hole;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素，或区间不存在if (begin >= end) {return;}//分割区间//int midi = PartSort_1(a, begin, end);int midi = PartSort_2(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi+1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi + 1, end);
}

递归版本三：前后指针法

大致思想：通过 prev 和 cur 下标指针，将每趟大于等于 a[keyi] 的值往后推，最后将基准值 a[keyi] 与 a[prev] 交换归位

//单趟分割区间
//前后指针法
int PartSort_3(int* a, int left, int right) {int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right) {cur 找小//while (cur < right && a[cur] >= a[keyi]) {//	cur++;//}//if (cur < right) {	//避免所有元素都大于 keyi//	prev++;//	Swap(&a[cur], &a[prev]);//}if (a[cur] < a[keyi]) {prev++;Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素，或区间不存在if (begin >= end) {return;}//分割区间//int midi = PartSort_1(a, begin, end);//int midi = PartSort_2(a, begin, end);int midi = PartSort_3(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi+1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi + 1, end);
}

时间复杂度（三个版本效率相同）

每趟区间分割创建函数栈帧的复杂度为二叉结构的高度 O(logn)，每趟区间分割确定一个数的位置 O(n)，所以是 O(n*logn)

但是如果数组有大量重复元素时，每次选择的 keyi 基准值都是同一个数；或者每次选择的 keyi 都是数组中最大或最小的元素，那么递归深度就会大大增加，时间复杂度变成 O(n^2)，比如下面的示意图

空间复杂度（三个版本效率相同）

取决于递归深度，即二叉结构高度 O(logn)

稳定性

涉及到元素之间的交换，不稳定

递归版本的优化

为了避免取基准值 keyi 时，出现取到最小或最大的情况，我们使用三数取中的方法

//三数取中
int GetMidIndex(int* a, int left, int right) {int midi = (left + right) / 2;if (a[left] > a[midi]) {Swap(&a[left], &a[midi]);	//此时 a[left] <= a[midi]}if (a[left] > a[right]) {Swap(&a[left], &a[right]);	//此时 a[left] <= a[right]}if (a[midi] > a[right]) {Swap(&a[right], &a[midi]);	//此时 a[midi] <= a[right]}return midi;
}

以版本三为例，应用

//单趟分割区间
//前后指针法
int PartSort_3(int* a, int left, int right) {int keyi = GetMidIndex(a, left, right);Swap(&a[keyi], &a[left]);int prev = left;int cur = prev + 1;keyi = left;while (cur <= right) {cur 找小//while (cur < right && a[cur] >= a[keyi]) {//	cur++;//}//if (cur < right) {	//避免所有元素都大于 keyi//	prev++;//	Swap(&a[cur], &a[prev]);//}if (a[cur] < a[keyi]) {prev++;Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;
}

非递归版本

考虑到递归会有栈溢出的风险，所以非递归版本，使用动态栈进行模拟

对栈有问题，请看之前的文章~

大致思想：见代码注释~

//非递归快排
void QuickSortNonR(int* a, int begin, int end) {//栈具有后进先出的性质//初始化一个动态栈Stack st;StackInit(&st);//将区间入栈StackPush(&st, end);StackPush(&st, begin);while (StackEmpty(&st)) {	//只要栈非空，子区间未分割完//从栈中取出一对区间int l = StackTop(&st);StackPop(&st);int r = StackTop(&st);StackPop(&st);//对这对区间分割int keyi = PartSort_3(a, l, r);//分割完之后，接着分割子区间// [l,keyi-1] keyi [keyi+1,r]//先让左右子区间入栈//避免区间不存在或者只有一个元素的情况if (keyi + 1 < r) {StackPush(&st, r);StackPush(&st, keyi + 1);}if (l < keyi - 1) {StackPush(&st, keyi - 1);StackPush(&st, l);}}StackDestroy(&st);
}