杭州哪个网站建设最好,崇州市建设局网站,班级优化大师头像,google adwords#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前正在学习c和算法 ✈️专栏#xff1a;数据结构 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有帮助… 个人主页Weraphael ✍作者简介目前正在学习c和算法 ✈️专栏数据结构 希望大家多多支持咱一起进步 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注 目录 一、hoare版本(左右指针法)1.1 算法思想1.2 hoare版本代码实现1.3 hoare版本性能分析 二、 基准值选取随机值(优化)三、三数取中优化四、小区间优化4.1 思想 五、三路划分优化六、快速排序之挖坑法6.1 算法思路6.2 代码实现 七、前后指针法最推荐的方法7.1 算法思路7.2 代码实现 八、非递归版快速排序8.1 前言8.2 实现方法8.3 代码实现 一、hoare版本(左右指针法)
1.1 算法思想
【思想】 任取待排序元素序列中的某元素作为 基准值key。一般是第一个元素和最后一个元素。 【✨重点】 将待排序集合 分割成两子序列。使得左子序列中所有元素均小于key右子序列中所有元素均大于key。
做法定义两个变量i和j分别指向开头和最后一个元素。请务必记住此结论如果选取的基准值是第一个元素要让j先动反之让i先动。假设选取的基准值为第一个元素并且要求序列为升序
若j遇到小于等于 key的数则停下然后i开始走直到i遇到一个大于key的数时将i和j的内容交换如果区间内还有元素则重复以上操作。最后你会发现i和j最后一定会相遇可以参考下面动图此时将相遇点的内容与key交换即可
最后左右子序列重复该过程直到所有元素都排列在相应位置上为止。递归
以下是一趟排序的动图演示 在往期博客中我写了一篇快排算法模板有兴趣的可以来看看点击跳转
1.2 hoare版本代码实现
#include stdio.hvoid Swap(int* x, int* y)
{int t *x;*x *y;*y t;
}// hoare版本
void quick_sort(int a[], int l, int r)
{// 如果区间只有一个元素或者没有元素就没必要排序了if (l r) return;// 1. 选取一个基准值(以选取第一个元素为例)int key a[l];// 2. 定义i和ji从左向右走j从右向左走。int i l, j r;while (i j){// 注意若选择第一个元素作为基准值则需要j先走反之让i先走while (i j a[j] key) // 找小{j--;}while (i j a[i] key) // 找大 {i;}// 交换if (i j)Swap(a[i], a[j]);}// 循环结束后i和j一定会相遇和基准值交换Swap(a[l], a[i]);// 3.递归quick_sort(a, l, i - 1);quick_sort(a, i 1, r);
} 【程序结果】 注意这里会有一个越界 死循环问题 我犯的错误 在while (i j a[j] key)循环中如果不加i j那么假设序列已经是升序了那么就会越界while (i j a[i] key)也同理 并且如果只写a[i] key将序列中出现数据冗余就会陷入死循环最后还有一个问题就是本人初学时犯的忽略了一个小的知识点qwq。
与基准值交换Swap(a[l], a[i])不能写成Swap(key, a[i])。因为key是一个局部变量只是存储序列a[l]虽然交换了但是序列第一个元素并没有改变。我也是通过调试发现的hh
1.3 hoare版本性能分析
时间复杂度
快速排序其实是二叉树结构的交换排序方法 递归的高度是logN而单趟排序基本都要遍历一遍序列大约有N个数因此时间复杂度是NlogN
接下来可以和堆排序以及希尔排序来比较一下它们三者的时间复杂度的量级都是NlogN 我们发现当数据个数为一百万的时候快速排序还是非常快的。不愧叫快排
那么快排最坏的情况是什么
最坏的情况即包括逆序也包括有序。其时间复杂度是O(N2) 如果数据量大的话那么栈一定会爆。那如果是这样快排还叫快排吗
先说结论快排的时间复杂度是O(NlogN)
那么如何解决这个问题呢通过分析发现有序和无序就是因为基准值选取的不好。
因此有人提出了优化基准值可以选取随机值或者三数取中
二、 基准值选取随机值(优化)
做法使用rand函数随机选取区间中的下标rand() % (r - l)但是这样远远不够因为递归的时候左区间会随之改变。因此正确下标取法rand() % (r - l) l
void quick_sort(int a[], int l, int r)
{if (l r) return;// 随机选key// 区间下标范围int randIdx (rand() % (r - l)) l; Swap(a[l], a[randIdx]);// 以下都和hoare版本一样int key a[l];int i l, j r;while (i j){while (i j a[j] key) {j--;}while (i j a[i] key){i;}Swap(a[i], a[j]);}Swap(a[l], a[i]);quick_sort(a, l, i - 1);quick_sort(a, i 1, r);
}【程序结果】 三、三数取中优化
三数取中是指第一个元素、最后一个元素和中间元素选出不是最小也不是最大的那一个找的是下标
int GetMinNum(int a[], int l, int r)
{int mid (l r) 1;// 选出不是最大也不是最小的// 两两比较if (a[l] a[mid]){if (a[mid] a[r]){return mid;}else if (a[r] a[l]){return l;}else{return r;}}else // a[l] a[mid]{if (a[l] a[r]){return l;}else if (a[r] a[mid]){return mid;}else{return r;}}
}void quick_sort(int a[], int l, int r)
{if (l r)return;// 三数取中int mid GetMinNum(a, l, r);Swap(a[mid], a[l]);// 以下和hoare版本一样int key a[l];int i l, j r;while (i j){while (i j a[j] key) {j--;}while (i j a[i] key){i;}Swap(a[i], a[j]);}Swap(a[l], a[i]);quick_sort(a, l, i - 1);quick_sort(a, i 1, r);
}【程序结果】 四、小区间优化
4.1 思想
由于快速排序是基于分治的思想。其实就是二叉树结构的交换排序方法。而我们知道二叉树最后一层的结点个数是占整个结点个数的一半。并且快排递归到最后每一个都是小区间但是每一个小区间都需要使用多次递归。这样的消耗确实挺大。
因此我们可以对小区间进行优化让小区间不要使用递归了直接使用插入排序来进行优化。因为小区间以及很接近有序了。使用插入排序最佳。当然区间不可以太大因为我们要考虑小区间直接插入的效率高于递归的效率
那区间的范围在多少合适呢— 大概在10左右就行
#include iostream
using namespace std;void Swap(int *x, int *y)
{int t *x;*x *y;*y t;
}int GetMinNum(int a[], int l, int r)
{int mid (l r) 1;// 选出不是最大也不是最小的// 两两比较if (a[l] a[mid]){if (a[mid] a[r]){return mid;}else if (a[r] a[l]){return l;}else{return r;}}else // a[l] a[mid]{if (a[l] a[r]){return l;}else if (a[r] a[mid]){return mid;}else{return r;}}
}void InsertSort(int a[], int n)
{for (int i 1; i n; i){int end i - 1;int tmp a[i];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}void QuickSort(int a[], int l, int r)
{if (l r)return;// 如果区间个数超过10就使用递归if ((l - r 1) 10){// 三数取中int mid GetMinNum(a, l, r);Swap(a[mid], a[l]);// 以下和hoare版本一样int key a[l];int i l, j r;while (i j){while (i j a[j] key){j--;}while (i j a[i] key){i;}Swap(a[i], a[j]);}Swap(a[l], a[i]);QuickSort(a, l, i - 1);QuickSort(a, i 1, r);}else{InsertSort(a l, r - l 1);}
}int main()
{int a[] {9, 8, 7, 6, 5, 4, 3, 2, 1};int n sizeof(a) / sizeof(a[0]);QuickSort(a, 0, n - 1);for (int i 0; i n; i){printf(%d , a[i]);}return 0;
}五、三路划分优化
这个优化是为了解决大量元素重复的问题这个博主还未学到。暂且先放放hh
六、快速排序之挖坑法
6.1 算法思路 【算法思路】
选取一个基准值并用一个变量保存这个基值一般是第一个元素或者是最后一个元素然后序列中基准值这个位置相当于是一个坑等待下一个元素填入如果选取的基准值是第一个元素老样子j要从右边向左开始找小如果找到小就将j指向的元素填入到坑中而此时 j这个位置是一个坑等待填入接下来就是i从左向右找大如果找到了大就将i指向的元素填入到坑中同理的i这个位置是一个坑等待填入最后i和j相遇并且一起站着一个坑位hole然后就把基准值key填入即可递归重复区间[l, hole - 1]和区间[hole 1, r]
本质上来说填坑法和hoare版本类似相比其更加容易理解
6.2 代码实现
void QuickSort5(int a[], int l, int r)
{if (l r) return;int x a[l];// 如果选择左端点为基准值// 那么坑位一开始是以基准值为下标int hole l;int i l, j r;while (i j){while (i j a[j] x) // 找小{j--;}// 循环结束后来到此处说明找到小了// 将小的填入上一个坑位// 再更新坑位a[hole] a[j];hole j;while (i j a[i] x){i;}// 和上同理a[hole] a[i];hole i;}// 最后i和j相遇一定会同站一个坑位// 将基准值填入坑位即可a[hole] x;// 递归QuickSort5(a, l, hole - 1);QuickSort5(a, hole 1, r);
}七、前后指针法最推荐的方法
7.1 算法思路 选出一个基准值key一般是最左边或是最右边的。起始时prev指针指向序列开头cur指针指向prev的下一个位置。若cur指向的内容小于keyprev先向后移动一位然后交换prev和cur指针指向的内容然后cur指针继续向后遍历若cur指向的内容大于key则cur指针直接向后遍历。因此可以得出结论cur本质就是在找小然后让小的往前靠若cur超出序列此时将key和prev指针指向的内容交换即可。
经过一次单趟排序最终也能使得key左边的数据全部都小于keykey右边的数据全部都大于key。
最后再重复以上操作直至序列只有一个数据或者序列没有数据时。递归区间[l, prev - 1]和[prev 1, r]
7.2 代码实现
void quick_sort(int a[], int l, int r)
{if (l r)return;// 1. 选出一个keyint key a[l];// 2. 起始时prev指针指向序列开头cur指针指向prev1。int prev l, cur prev 1;while (cur r){// 3. 若cur指向的内容小于key// 则prev先向后移动一位// 然后交换prev和cur指针指向的内容// 然后cur指针(可以归到第四点)if (a[cur] key){prev;Swap(a[prev], a[cur]);}// 4. 若cur指向的内容大于key则cur指针直接cur;}// 若cur到达r 1位置此时将key和prev指针指向的内容交换即可。Swap(a[l], a[prev]);// 递归quick_sort(a, l, prev - 1);quick_sort(a, prev 1, r);
}八、非递归版快速排序
8.1 前言
我们知道递归会建立函数栈帧递归层越深占用栈区的空间就会越大栈的大小一般是8M或者10M。当深度足够深时栈区的空间就会被用完导致栈溢出。所有最稳妥的方法就是使用非递归。
老实讲快速排序一般不会发生栈溢出。因为大多数语言的快速排序算法的底层都是使用递归。
那么为啥还需要使用非递归来实现一遍呢因为往后如果递归发生栈溢出就得使用非递归。因此大家平常可以练习将递归改为非递归另外有些面试官为了考察代码能力偶尔会叫我们手撕一个非递归版快速排序。
8.2 实现方法
快速排序的递归算法主要是在划分子区间如果要非递归实现快速排序只需要使用一个栈来维护一个区间即可。注意要先入右区间再如左区间。而栈又是先进后出的因此满足递归是先展开左再展开右
ps一般将递归程序改为非递归首先想到就是栈。因为递归本身就是一个压栈的过程。
更详细的步骤在代码注释里
8.3 代码实现
#include iostream
#include stack
using namespace std;int GetMinNum(int a[], int l, int r)
{int mid (l r) 1;// 选出不是最大也不是最小的// 两两比较if (a[l] a[mid]){if (a[mid] a[r]){return mid;}else if (a[r] a[l]){return l;}else{return r;}}else // a[l] a[mid]{if (a[l] a[r]){return l;}else if (a[r] a[mid]){return mid;}else{return r;}}
}void Quick_sort(int a[], int l, int r)
{// 1. 用栈存储区间stackint st;// 2. 起始时区间一定是存在的// 先入右再如左st.push(r);st.push(l);// 如果栈不为空说明还有区间需要排序while (!st.empty()){// 3. 取出区间 栈顶一定是左区间int begin st.top();st.pop();int end st.top();st.pop();// 4. 对取出的区间进行单趟排序// 以下内容就是三数取中的内容 int mid GetMinNum(a, begin, end);swap(a[mid], a[begin]);int key a[begin];int i begin, j end;while (i j){while (i j a[j] key)j--;while (i j a[i] key)i;if (i j)swap(a[i], a[j]);}swap(a[begin], a[i]);// 5. 更新栈(更新区间) // [begin,i - 1] [i] [i 1, end]// 先让右区间[i 1, end]入栈 // 如果区间内有数则入栈// 判断条件写不写等都一样一个数没必要排序if (i 1 end) {st.push(end);st.push(i 1);}if (begin i - 1){st.push(i - 1);st.push(begin);}}
}【程序结果】
