欢迎来到天天文库
浏览记录
ID：13628226
大小：21.02 KB
页数：3页
时间：2018-07-23
《【昊昊带你学】常见的几种排序2(qsort)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Qsort快排，顾名思义，它是排序算法，而且它快，是吧。那这个快从何说起呢？写到这我才发现，说前面几个算法的时候，对时效只字未提，0.0证明昊昊的确是灰常不合格的程序猿。插入，选择，冒泡，blabla~我们把它们看做O(n^2)的算法，这里的这个O是个渐进记号，表示的是渐进上界，当然还有一种Θ，它同时渐进地给出了函数的上界及下界。严谨的判断方法当然应该讲算法运行步数表示成一个跟输入规模n有关的函数。当然，精确地计算看起来很麻烦，当n→∞时，许多项可以忽略，再把系数啥的忽略了，就得到上面的O()了（
2、好像是这么回事，这就是我当初在概论里没说这事儿的原因，我自己也不是啥细节都清楚）。而Qsort的效率就要高很多，平均O(nlogn)。不随机的情况下，最坏情况貌似也是O(n^2)。下面就进入正题：qsort！基本描述首先要说的是，快排也是基于分治思想的。它分为几个步骤，首先对要排序数组划分（先找出一个pivot（不知道该肿么翻，总之是用来作为比较的标准），将比pivot小的挪到pivot的一侧，其他到pivot的另一侧）。然后再递归地用qsort来排序pivot两边的数组。边界可以设成一个数、两个
3、数，也可以设成小于某个量的时候该用插入排序之类的，它们开销比较小，在小规模的时候不逊于快排。实现我们把分划的那一步单独拿出来，称作PARTITION(A,p,r)，它返回的是pivot的坐标。假设我们已经完成了这个函数，我们来看一看快排要怎样完成工作，伪代码如下：QUICKSORT(A,p,r)Ifp4、候，没有很好的接受递归、分治的思想，接受之后这些都是理所当然了哈~仔细来看一下。上面这个伪代码对边界没有特别处理，指针交叉了就完事儿。在工作时（p为左边界，r为又边界），分划过后，q得到pivot的位置。此时数组的情况是，q左边的都小于pivot，q右边的都大于pivot（假设从小到大）。排序p到r数组的问题，就成功的被分解成了排序p到q-1数组以及排序q+1到r数组。不断分划，数组长度越来越短，当p==r时，q==p==r。那么再向下调用QUICKSORT()时就停止了。循环不变的证明就不抄了，5、我自己是写不出来那么严谨的证明，详细证明大家可以google之类的查查资料吧。接下来就是算法中关键的部分，PARTITION分划！伪代码如下：PARTITION1(A,p,r)X←A[r]I←p-1Forj←ptor-1DoifA[j]<=xTheni←i+1ExchangeA[i]↔A[j]ExchangeA[i+1]↔A[r]Returni+1注意这是PARTITION1，我常用的不是这个，不过既然《导论》先介绍它，我也把它放到前面来说吧。上来两个变量，XI。X作为pivot使用，而i则是分界6、线，从左向右扫。工作时，j左侧是已经分划的一部分，其中i左侧的数小于X，当j扫到r-1时，i左侧都小于X，所以将A[i+1]与A[r]交换，此时，就分划完成了。同样，这不是严格的循环不变式证明，只是大体有个框框，说明一下这个分划的正确性。PARTITION2(A,p,r)X←A[p]I←p-1J←r+1WhieTRUEDorepeatj←j–1UntilA[j]<=xRepeatI←I+1Untila[i]>=xIfI7、初的那个版本0.0。首先X是pivot，毫无疑问。然后左右指针分别是Ij。左右指针分别向中间扫，j扫到一个小于等于X的停下，i扫到一个大于等于X的停下。俩指针交换一下继续，知道指针交叉，返回j。举例（PARTITION1）1)28713568、4Ip,jr2)29、87135610、4I,pjr3)211、812、7135613、4I,pjr4)214、8715、135616、4I,pjr5)2117、7818、35619、4pijr6)21320、8721、5622、4pijr7)21323、87524、625、4pijr8)21326、875627、4pir9)21328、29、430、7568pir好吧，我只能尽力做成这样了0.0我觉得大家应该能看懂吧。每个步骤包含两行，第一行是当前数组状态，第二行是各个指针状态。”31、”将数组分割成若干段。最右边的”32、”表示j只能扫到6，而不会扫到最右的数。然后最左面的”33、”跟着i，意味着它左边的数都小于4。中间的”34、”跟着j，就是说它左边的都已经分划好了。9）处，4已经找到正确位置，左”35、”的左侧都小于4，右”36、”的右侧都大于4。此时就可以返回i+1了，正好是4（pivot）的位置。快排应该算是一个非常重要的算法，估计咱
4、候，没有很好的接受递归、分治的思想，接受之后这些都是理所当然了哈~仔细来看一下。上面这个伪代码对边界没有特别处理，指针交叉了就完事儿。在工作时（p为左边界，r为又边界），分划过后，q得到pivot的位置。此时数组的情况是，q左边的都小于pivot，q右边的都大于pivot（假设从小到大）。排序p到r数组的问题，就成功的被分解成了排序p到q-1数组以及排序q+1到r数组。不断分划，数组长度越来越短，当p==r时，q==p==r。那么再向下调用QUICKSORT()时就停止了。循环不变的证明就不抄了，
5、我自己是写不出来那么严谨的证明，详细证明大家可以google之类的查查资料吧。接下来就是算法中关键的部分，PARTITION分划！伪代码如下：PARTITION1(A,p,r)X←A[r]I←p-1Forj←ptor-1DoifA[j]<=xTheni←i+1ExchangeA[i]↔A[j]ExchangeA[i+1]↔A[r]Returni+1注意这是PARTITION1，我常用的不是这个，不过既然《导论》先介绍它，我也把它放到前面来说吧。上来两个变量，XI。X作为pivot使用，而i则是分界
6、线，从左向右扫。工作时，j左侧是已经分划的一部分，其中i左侧的数小于X，当j扫到r-1时，i左侧都小于X，所以将A[i+1]与A[r]交换，此时，就分划完成了。同样，这不是严格的循环不变式证明，只是大体有个框框，说明一下这个分划的正确性。PARTITION2(A,p,r)X←A[p]I←p-1J←r+1WhieTRUEDorepeatj←j–1UntilA[j]<=xRepeatI←I+1Untila[i]>=xIfI7、初的那个版本0.0。首先X是pivot，毫无疑问。然后左右指针分别是Ij。左右指针分别向中间扫，j扫到一个小于等于X的停下，i扫到一个大于等于X的停下。俩指针交换一下继续，知道指针交叉，返回j。举例（PARTITION1）1)28713568、4Ip,jr2)29、87135610、4I,pjr3)211、812、7135613、4I,pjr4)214、8715、135616、4I,pjr5)2117、7818、35619、4pijr6)21320、8721、5622、4pijr7)21323、87524、625、4pijr8)21326、875627、4pir9)21328、29、430、7568pir好吧，我只能尽力做成这样了0.0我觉得大家应该能看懂吧。每个步骤包含两行，第一行是当前数组状态，第二行是各个指针状态。”31、”将数组分割成若干段。最右边的”32、”表示j只能扫到6，而不会扫到最右的数。然后最左面的”33、”跟着i，意味着它左边的数都小于4。中间的”34、”跟着j，就是说它左边的都已经分划好了。9）处，4已经找到正确位置，左”35、”的左侧都小于4，右”36、”的右侧都大于4。此时就可以返回i+1了，正好是4（pivot）的位置。快排应该算是一个非常重要的算法，估计咱
7、初的那个版本0.0。首先X是pivot，毫无疑问。然后左右指针分别是Ij。左右指针分别向中间扫，j扫到一个小于等于X的停下，i扫到一个大于等于X的停下。俩指针交换一下继续，知道指针交叉，返回j。举例（PARTITION1）1)2871356
8、4Ip,jr2)2
9、871356
10、4I,pjr3)2
11、8
12、71356
13、4I,pjr4)2
14、87
15、1356
16、4I,pjr5)21
17、78
18、356
19、4pijr6)213
20、87
21、56
22、4pijr7)213
23、875
24、6
25、4pijr8)213
26、8756
27、4pir9)213
28、
29、4
30、7568pir好吧，我只能尽力做成这样了0.0我觉得大家应该能看懂吧。每个步骤包含两行，第一行是当前数组状态，第二行是各个指针状态。”
31、”将数组分割成若干段。最右边的”
32、”表示j只能扫到6，而不会扫到最右的数。然后最左面的”
33、”跟着i，意味着它左边的数都小于4。中间的”
34、”跟着j，就是说它左边的都已经分划好了。9）处，4已经找到正确位置，左”
35、”的左侧都小于4，右”
36、”的右侧都大于4。此时就可以返回i+1了，正好是4（pivot）的位置。快排应该算是一个非常重要的算法，估计咱
此文档下载收益归作者所有
