网站建设公司团队简介,网站seo基础优化,搜狗推广代理商查询,公众号平台网站开发正如上一篇博文所说#xff0c;今天我们来讨论一下所谓的“高级排序”——快速排序。首先声明#xff0c;快速排序是一个典型而又“简单”的分治的递归算法。 递归的威力我们在介绍插入排序时相比已经见识过了#xff1a;只要我前面的队伍是有序的#xff0c;我就可以通过向… 正如上一篇博文所说今天我们来讨论一下所谓的“高级排序”——快速排序。首先声明快速排序是一个典型而又“简单”的分治的递归算法。 递归的威力我们在介绍插入排序时相比已经见识过了只要我前面的队伍是有序的我就可以通过向前插队来完成“我的排序”至于前面的队伍怎么有序……递归实现我不管。 递归就是如此“简单”的想法我不管需要的条件怎么来的反正条件的实现交给“递归的小弟们”去做只要有基准情形并且向着基准情形“递”去就可以保证“归”回我一个需要的条件。 不过插入排序虽然体现出了递归的想法却没有解释什么叫“分治”其实分治就是分而治之的意思。如果要举个例子的话恐怕汉诺塔是最为合适的毕竟大家学习C语言递归时应该都接触过。 汉诺塔的递归解法用大白话来说就是作为老和尚我希望自己只用做一件事就是把最底下的盘子移到C柱去至于上面的盘子怎么移到B柱交给小和尚A去做而我把最底下的盘子移到C柱后B柱的盘子们怎么移到C柱来交给小和尚B去做。 上述汉诺塔的解法就是一种“分治”把上层盘子移到B柱的任务“分给”A去“治”而把B柱的盘子们移到C柱的任务又“分给”B去“治”我只要把底下的盘子移到C柱就行了。需要注意的是分治不需要什么基准情形其本质就是将一个大的任务分成两个或多个小的子任务在子任务完成的情况下去更简单地解决大任务。一般来说分治总是与递归同时出现即“分治之后递归完成”。 那么快速排序又是怎样的一个分治、递归呢我们就用大白话来说说快速排序的想法 对于数组a我随便选一个元素a[x]作为枢纽所有小于枢纽的元素都“站左边去”所有大于枢纽的元素都“站右边去”分治小于枢纽的元素们给我“自行”排好队大于枢纽的元素们也给我“自行”排好队递归。若小于a[x]的元素共有i个则它们放在a[0]到a[i-1]而后将a[x]放在a[i]处大于a[x]的放于a[i1]到a[size-1]处i如何确定暂时不管 既然有递归那么就必须有基准情形那么快速排序的基准情形会是什么呢显然是当数组被“递”得只有3个元素的时候此时对该数组进行“分治”就会直接完成排序。 我们先来试着给出快速排序的伪代码调用者调用方式为QuickSort(a,0,size-1) void QuickSort(int *a, unsigned int left,unsigned int right)
{//若a[left]到a[right]元素个数大于2则继续分治、递归if (left rightleft ! right - 1){/*伪代码随机选一个a[x]要求xleftxright作为枢纽*//*伪代码将a[left]到a[right]中所有小于median的元素置于a[left]到a[i-1]处i未知*//*伪代码将a[left]到a[right]中所有大于median的元素置于a[i1]到a[right]处*/ /*伪代码将a[x]放在a[i]处*/QuickSort(a, left, i - 1);QuickSort(a, i 1, right);}//若a[left]到a[right]元素个数恰为2则直接排序else if (left right - 1){if(a[left]a[right])swap(a[left], a[right]);}//若leftright则说明只有一个元素已为“有序”
} 虽然快速排序的想法看似比较简单但其实现还是有“坑”与“捷径”的接下来我们就一步一步实现快速排序看看都有什么“坑”与“捷径”。 回顾快速排序的想法和伪代码可以看出其第一步就是“随便选一个a[x]”这看似简单的第一步其实是一个“坑”因为虽说是随便选但“选一个a[x]”还是要写出具体代码来的所以随便选一个枢纽的代码该如何写就有了三种做法 1.既然是随便选那就直接选a[left]好了。 这个做法是最不可取的原因非常简单假设数组已经接近有序那么选取a[left]作为枢纽就很容易导致分治变得“无效”因为a[left]很可能就是最小的元素。 2.既然要随便选那就选a[rand()%(right-left1)]好了 这个做法可取但是问题出在计算随机数上计算随机数多少需要一点代价而且计算随机数对于排序这件事并没有直接帮助。 3.三数中值法 很显然这就是我们的主角了。相比于方法1本方法要更加安全而相比于方法2本方法要更加廉价并且可以帮助到排序本身。那么三数中值法究竟是怎样的呢其实就是令center(leftright)/2然后选a[left]、a[center]、a[right]三者的中值作为枢纽。不过在选取中值的同时我们也获取了这三者的大小信息因此可以顺便将这三者“放好位置”所以说相比于方法2本方法对于排序要更有帮助一些。 三数中值法我们一般用一个单独的函数来实现其返回值即枢纽的值 int MedianOf3(int *a, unsigned int left, unsigned int right)
{unsigned int center (left right) / 2;//前两个if保证a[left]存储着三数最小值//最后一个if保证a[center]为三数中值a[right]为三数最大值//三个if不仅选出了枢纽同时将另外两元素的分治工作完成if (a[left] a[center])swap(a[left],a[center]);if (a[left] a[right])swap(a[left],a[right]);if (a[center] a[right])swap(a[center],a[right]);//最后将枢纽与a[right-1]交换即“将枢纽放在a[right-1]处”swap(a[center],a[right-1]);return a[right-1];
} 在三数中值法的代码中最后我们将枢纽放在了a[right-1]处这是为什么呢接下来的讲解可以解释这个做法的原因。 实现了枢纽的选取后接下来要实现的就是分治的“分”在上述快速排序的想法中我们说过我们将小于枢纽的元素们放在a[left]至a[i-1]处枢纽放在a[i]处大于枢纽的元素们放在a[i1]至a[right]处。但是问题来了怎么确定i的值呢其实可以肯定的是在开始分治与枢纽的比较前i是绝对不可能知道的。只有所有元素都与枢纽比较完了才知道i到底是多少。 不过既然肯定了必须比完才知道那我们就“比完再知道”呗。具体想法就是 1.先令枢纽与a[right-1]交换即将枢纽暂且放在a[right-1]处在三数中值代码中已经完成此步骤 2.设变量l_pos从left1开始递增直观地说就是“让l_pos从数组左侧开始向右逐个扫描元素”a[left]已经在三数中值时分治完毕不需要再扫描 若l_pos扫描到a[l_pos]枢纽则l_pos暂停扫描 3.设变量r_pos从right-2开始递减直观地说就是“让r_pos从数组右侧开始向左逐个扫描元素”a[right]已分治a[right-1]为枢纽 若r_pos扫描到a[r_pos]枢纽则r_pos暂停扫描 4.当l_pos与r_pos均停止时若元素互异必然存在此情况若l_posr_pos直观地说就是它们“尚未碰头”则交换a[l_pos]与a[r_pos]然后l_pos继续向右扫描r_pos继续向左扫描。若l_posr_pos则它们“已经碰头”此时应有l_posr_pos1即l_pos就在r_pos右边于是我们彻底停止两者的扫描并确定了i的值为此时的l_pos。 画图三张以兹参考 图1表示一种初始状态 图2表示当a[l_pos]枢纽a[r_pos]枢纽且尚未结束时 图3表示结束情况 对应的分治部分代码就是这样 //初始化l_pos与r_pos
unsigned int l_pos left 1, r_pos right - 2;
//根据三数中值法得出枢纽同时完成两个元素的分配
int median MedianOf3(a, left, right);//l_pos与r_pos不断向中间扫描
while (1)
{while (a[l_pos] median)l_pos;while (a[r_pos] median)r_pos;//l_pos与r_pos均暂停扫描的两种情况if (l_pos r_pos)swap(a[l_pos], a[r_pos]);elsebreak;
}
//最后记得将枢纽交换至正确位置
swap(a[l_pos], a[right - 1]); 解决了选取枢纽与分治快速排序就算是完成了从之前所给的快速排序伪代码就可以看出这一点伪代码中没有解决的就是这两个地方 void QuickSort(int *a, unsigned int left,unsigned int right)
{if (left rightleft ! right - 1){//选枢纽 //随机选一个a[x]要求xleftxright作为枢纽median//分治 //将a[left]到a[right]中所有小于median的元素置于a[left]到a[i-1]处//将a[left]到a[right]中所有大于median的元素置于a[i1]到a[right]处//将a[x]放在a[i]处 //递归QuickSort(a, left, i - 1);QuickSort(a, i 1, right);}else if (left right - 1){if(a[left]a[right])swap(a[left], a[right]);}
} 将伪代码中未完成部分填上就有了如下快速排序 void QuickSort(int *a, unsigned int left, unsigned int right)
{//若a[left]到a[right]元素个数大于2则继续分治、递归if (left rightleft ! right - 1){/*——————选枢纽——————*/int median MedianOf3(a, left, right);//根据三数中值法得出枢纽同时完成两个元素的分配/*——————分治——————*/unsigned int l_pos left 1, r_pos right - 2;//初始化l_pos与r_pos//l_pos与r_pos不断向中间扫描while (1){while (a[l_pos] median)l_pos;while (a[r_pos] median)r_pos;//l_pos与r_pos均暂停扫描的两种情况if (l_pos r_pos)swap(a[l_pos], a[r_pos]);elsebreak;}//最后记得将枢纽交换至正确位置swap(a[l_pos], a[right - 1]);/*——————递归——————*/QuickSort(a, left, l_pos - 1);QuickSort(a, l_pos 1, right);}//若a[left]到a[right]元素个数恰为2则直接排序else if (left right - 1){if (a[left]a[right])swap(a[left], a[right]);}//若leftright则说明只有一个元素已为“有序”
} 但是请注意上述代码是有问题的这是不容易察觉的第二个坑坑在何处呢让我们揪出上述代码的一部分 while (1){while (a[l_pos] median)l_pos;while (a[r_pos] median)r_pos;//l_pos与r_pos均暂停扫描的两种情况if (l_pos r_pos)swap(a[l_pos], a[r_pos]);elsebreak;} 如果数组的元素一定互异那么这一部分代码没有问题但是如果数组元素存在相同那么这部分代码就可能出现问题。 假设l_pos暂停了扫描原因是a[l_pos]median而且r_pos也暂停了扫描并且也是因为a[r_pos]median那么单纯交换a[l_pos]与a[r_pos]只会使循环陷入死循环因为两个子循环的判断条件将永远为false从而l_pos与r_pos一直不变。 那么该如何解决这个问题呢最直接的办法就是增加新的判断判断a[l_pos]与a[r_pos]是否都与median相等如果是则不交换两者改为令l_pos和r_pos--。 但是实际上我们存在一个解决此问题的捷径这个捷径的思路解说起来稍显麻烦既然问题是出在交换后l_pos与r_pos不会变化递增与递减那就在子循环处改为先变化再比较不就好了 while (1){while (a[l_pos] median)/*Do nothing*/;while (a[--r_pos] median)/*Do nothing*/;if (l_pos r_pos)swap(a[l_pos], a[r_pos]);elsebreak;} 同时因为l_pos与r_pos都变成了“先变化再比较”所以两者的初始值也要改变为 unsigned int l_pos left, r_pos right - 1; 于是完整的快速排序就实现好了代码如下 void QSort(int *a, unsigned int left, unsigned int right)
{if (left rightleft ! right - 1){unsigned int l_pos left, r_pos right - 1;int median MedianOf3(a, left, right);int temp;while (1){while (a[l_pos] median);while (a[--r_pos] median);if (l_pos r_pos){temp a[l_pos];a[l_pos] a[r_pos];a[r_pos] temp;}elsebreak;}temp a[l_pos];a[l_pos] a[right - 1];a[right - 1] temp;QSort(a, left, l_pos - 1);QSort(a, l_pos 1, right);}else if (left right - 1 a[left] a[right]){int temp a[left];a[left] a[right];a[right] temp;}
} 为了方便调用者我们可以实现一个简单的“接口” void QuickSort(int *a, unsigned int size)
{return QSort(a, 0, size - 1);
} 对于快速排序还要注意的一点是当数组的大小N很小时快速排序是不如插入排序的并且需要注意的是由于快速排序的递归必然会出现“小数组”。因此实际实现快速排序时往往选择对小数组执行一个插入排序。即 void QSort(int *a, unsigned int left, unsigned int right)
{if (left right-N){//此部分代码略}else{InsertionSort(a,right-left1);}
} 至此快速排序实现完毕。 接下来我们试着分析一下快速排序的时间复杂度。这一部分我们将分为两个小部分快速排序的最坏情况快速排序的最好情况。 首先为了方便分析我们假设快速排序的枢纽选择是完全随机的。对于大小为N的数组快速排序耗时设为T(N)则T(1)1。于是T(N)T(i)T(N-i-1)c*N其中i为小于枢纽的元素个数c为未知常数c*N代表分治阶段耗费的线性时间。 那么快速排序的最坏情况就是每一次选取的枢纽都是最小的元素此时i0上述公式变为 T(N)T(N-1)c*N递推此公式可得 T(N-1)T(N-2)c*(N-1) T(N-2)T(N-3)c*(N-2) …… T(2)T(1)c*2 将上述公式左侧与右侧均全部相加得 T(N)T(N-1)T(N-2)……T(2) T(N-1)T(N-2)……T(2)T(1)c*(2345……N) 化简可得 T(N)T(1)c*(234……N)1c*(234……N)O(N2) 也就是我们在上一篇博文提到的快速排序最坏情况为O(N2) 不难看出选择枢纽时不论是完全随机还是三数中值快速排序都不容易出现这样的最坏情况。 接下来我们看看快速排序的最好情况。快速排序的最好情况显然就是每次枢纽都选择了整个剩余数组的中间值为了简化推导我们假定递归时将枢纽本身也带进去并且N为2的幂。从而 T(N)2*T(N/2)c*N 两边同时除以N得 T(N)/NT(N/2)/(N/2)c递推此公式可得 T(N/2)/(N/2)T(N/4)/(N/4)c T(N/4)/(N/4)T(N/8)/T(N/8)c …… T(2)/2T(1)/1c 将上述公式左侧与右侧均全部相加 得 T(N)/NT(N/2)/(N/2)……T(2)/2T(N/2)/(N/2)……T(1)/1c*logN 化简得 T(N)/NT(1)/1c*logN即T(N)N*c*logNO(N*logN)。所以快速排序的最好情况就是O(N*logN)。 快速排序的平均情况分析的公式繁杂且化简需要高深的数学此处只给出基本思路既然枢纽是随机的那么小于枢纽的元素个数i就也是随机位于[0,N-1]那么i的平均值就应该是(012……(N-1))/N同理大于枢纽的元素个数平均值为(012……(N-1))/N基于这两点T(N)2*(012……(N-1))/Nc*N依据此公式进行递推、相加、化简可以得出平均时间为O(N*logN) 对于快速排序的分析并不是只有本文所提比如在l_pos于r_pos扫描的过程中我们为什么选择在a[l_pos]或a[r_pos]等于median时停下而不是继续扫描呢这是有原因的简述就是防止极端情况下l_pos及r_pos越界同时使分得的两个子数组大小更加平衡。但是更多的分析本文就不做介绍了时间有限╮(╯_╰)╭ 最后对于大小为20万的随机整数数组我们提过的“主流”排序算法的简单比较结果如下仅供参考 转载于:https://www.cnblogs.com/mm93/p/7569529.html
