冒泡排序
冒泡排序(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);
}