快速排序的本质是从数组中选一个参考值ref,比该参考值的大的,将其放在ref的右边,比ref小的放在左边,然后不断的对两边重复执行该动作
我们先列出来快速排序的步骤:
1.从数组中选一个参考值ref,比该参考值的大的,将其放在ref的右边,
上面的动作将数组划分为两部分:
A ref B
A是比ref小的数组元素集合,它仍然是数组,B是比ref大的元素集合,它也仍然是数组
2.在对ref左右两边的元素重复上述动作,直到A和B都只剩下一个元素,那么排序就算完成了。
重点是如何分别选出来两个集合A和B。算法导论里面把这个步骤叫做partition动作。
先把算法导论里面的伪代码贴出来,大家先看一下:
先看第一种ref的选择方法,即ref = a[r]
partition(a[], p, r) { i = p j = p-1 ref = a[r] for(; i<r; i++) { if(a[i]<ref) { j++ exchange(a[i], a[j]) } } exchange(a[r], a[j+1]) return j+1; }
首先找一个参考值,ref = a[r],为了简单起见,这里取最后一个作为参考值,实际上可以去任意一个值作为参考值。这个我们一会再说。
然后找定义两个游标,分别是i 和j。i=p, j=p-1。为什么要这么定义呢?原因是我们既然选的是第一个,也就是a[p],同时表示是从数组的第一个元素开始遍历的。
选取j的目的是,我们要时刻知道当前最近一次比ref小的值的位置。由于我们选取的是a[r],作为参考值,且从第一个元素开始遍历,为了跟踪最近一次比ref小的数的游标,暂时j=p-1。大家可以仔细体会一下这个做的意义。
观察上述代码可以看到,j总是记录着最近一次比ref小的数的游标,因此最后return j+1,所有比ref小的数的游标均小于j+1,所有比ref大的数的游标均大于j+2。
总之我们执行partition的目的就是为了得到A,B,以及中间数的游标,这样我们就可以分别对A和B重复执行上述动作。
接下来我们考虑另外两种选取ref的方法。从上面选取最后一个值a[r],作为参考值,并且在最后,将a[r]和a[j+1]交换的动作可以知道,我们总是希望知道我们选取参考值在partition过程中的位置,以便我们可以在最后一步,将a[refId] 和 a[j+1]的值交换。这里的refId表示选取ref值在a[]中的游标。
如果我们选取ref为最后一个值,那么在所有的partition过程中,这个值的位置是固定的。但是,假如我们选取的ref的refId是p到r范围内的一个随机数呢?
显然,假如我们随机选取ref的值,那么在partition过程中,refId对于的ref就有可能和其他值交换。这时候我们就需要更新ref对应的游标。
这样一来,思路就很清晰了。
先给出partition的伪代码:
partition(a[], p, r){ refId = random(p,r) i = p j = p-1 for(; i<=r; i++) { if(a[i]<ref) { j++ if(j == refId)//此时j刚好等refId,并且要和a[i]交换,则更新refId { refId = i } exchange(a[i], a[j]) } } exchange(a[j+1], a[refId]) return j+1 }
从三种选择ref的方法可以看到本质上都是一样的,都为用一个游标j记录最近一次遍历到的比ref小的数据的游标,然后将ref和a[j+1]交换,返回j+1。
下面给出C++的代码实现
#include <iostream> #include <stack> #include"stdlib.h" #include <time.h> using namespace std; template<class T> class SORT { public: static void myQsort(T a[], int p, int r); static void myQsortNoRecur(T a[], int p, int r); private: static int partition(T a[], int p, int r); static void exchange(T a[], int i, int j); }; template<class T> void SORT<T>::exchange(T a[], int i, int j) { T temp = a[i]; a[i] = a[j]; a[j] = temp; return; } template<class T> int SORT<T>::partition(T a[],int p,int r) { int i = p; int j = p-1; T ref = a[p]; int refId = p; srand((unsigned)time(NULL)); refId = (rand() % (r-p+1))+ p; //cout<<refId<<endl; ref = a[refId]; for(; i<=r; i++) { if(a[i] < ref) { j++; exchange(a, i, j); if(j == refId) { refId = i; } } } exchange(a, j+1, refId); return j+1; } template<class T> void SORT<T>::myQsort(T a[],int p,int r) { int q = 0; if(p<r) { q = partition(a, p, r); myQsort(a, p, q-1); myQsort(a, p+1, r); } return; } template<class T> void SORT<T>::myQsortNoRecur(T a[], int p, int r) { int start = p; int end = r; int mid = 0; std::stack<int> sortStk; sortStk.push(p); sortStk.push(r); while(!sortStk.empty()) { end = sortStk.top(); sortStk.pop(); start = sortStk.top(); sortStk.pop(); if(start < end) { mid = partition(a, start, end); sortStk.push(start); sortStk.push(mid -1); sortStk.push(mid + 1); sortStk.push(end); } } } int main(int argc, char** argv) { int a[10]; int b[10]; srand((unsigned)time(NULL)); for(int i=0; i<9; i++) { a[i] = rand(); } srand((unsigned)time(NULL)); for(int i=0; i<9; i++) { b[i] = rand(); } SORT<int>::myQsort(a,0, 9); SORT<int>::myQsortNoRecur(b,0, 9); for(int i=0; i<10; i++) { cout<<a[i]<<" "; } cout<<endl; for(int i=0; i<10; i++) { cout<<b[i]<<" "; } return 0; }
上面的代码我直接给出了快速排序的递归和非递归实现。
递归的实现方式很好理解,但是加入别人正在面试你快速排序算法的时候,多半会让你用非递归的方式实现给他看。下面我们就讨论一下。
先观察一下递归算法的运行过程,即每次都去对一段更小的范围去调用partition函数。所以我们需要知道每一次调用partition函数的start和end游标,同时,每一次partition调用都会产生新的start和end游标。
template<class T> void SORT<T>::myQsort(T a[],int p,int r) { int q = 0; if(p<r) { q = partition(a, p, r); myQsort(a, p, q-1); myQsort(a, p+1, r); } return; }
这样的话,我们就可以用一个通用容器去存放每次调用partition生成的start和end游标。知道虽有的合法的start和end游标都作为参数调用了partition函数。所谓合法的start和end就是start < end。。。。。
关于递归算法的非递归实现,第一个想到的数据结构肯定是栈。其实别的数据结构,例如队列,也是可以实现。这里给出基于stl内的stack的实现方法。代码如下
template<class T> void SORT<T>::myQsortNoRecur(T a[], int p, int r) { int start = p; int end = r; int mid = 0; std::stack<int> sortStk; sortStk.push(p); sortStk.push(r); while(!sortStk.empty()) { end = sortStk.top(); sortStk.pop(); start = sortStk.top(); sortStk.pop(); if(start < end) { mid = partition(a, start, end); sortStk.push(start); sortStk.push(mid -1); sortStk.push(mid + 1); sortStk.push(end); } } }
上面代码的运行过程就是每次循环,从容器内拿一个start和end,如果是合法的,就依次将他们再次放入容易,知道这个容器为空未知。
给个运行实例吧,我在代码里面实现的是实现随机数排序,ref采用随机选取的方式。
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
稳了!魔兽国服回归的3条重磅消息!官宣时间再确认!
昨天有一位朋友在大神群里分享,自己亚服账号被封号之后居然弹出了国服的封号信息对话框。
这里面让他访问的是一个国服的战网网址,com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后,确实是网易的网址,也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情,因为以前都没有出现这样的情况,现在突然提示跳转到国服战网的网址,是不是说明了简体中文客户端已经开始进行更新了呢?
更新日志
- 小骆驼-《草原狼2(蓝光CD)》[原抓WAV+CUE]
- 群星《欢迎来到我身边 电影原声专辑》[320K/MP3][105.02MB]
- 群星《欢迎来到我身边 电影原声专辑》[FLAC/分轨][480.9MB]
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 群星《2024好听新歌42》AI调整音效【WAV分轨】
- 王思雨-《思念陪着鸿雁飞》WAV
- 王思雨《喜马拉雅HQ》头版限量编号[WAV+CUE]
- 李健《无时无刻》[WAV+CUE][590M]
- 陈奕迅《酝酿》[WAV分轨][502M]
- 卓依婷《化蝶》2CD[WAV+CUE][1.1G]
- 群星《吉他王(黑胶CD)》[WAV+CUE]
- 齐秦《穿乐(穿越)》[WAV+CUE]
- 发烧珍品《数位CD音响测试-动向效果(九)》【WAV+CUE】
- 邝美云《邝美云精装歌集》[DSF][1.6G]
- 吕方《爱一回伤一回》[WAV+CUE][454M]