如何在电影网站中做淘客,怎么在百度免费推广,高端网站制作多少钱,国外网站怎么注册高速排序算法作者 July 二零一一年一月四日------------------------------------------写之前#xff0c;先说点题外话。每写一篇文章#xff0c;我都会遵循下面几点原则#xff1a;一、保持版面的尽量清晰#xff0c;力保排版良好。二、力争所写的东西#xff0c;清晰易… 高速排序算法 作者 July 二零一一年一月四日------------------------------------------ 写之前先说点题外话。每写一篇文章我都会遵循下面几点原则一、保持版面的尽量清晰力保排版良好。二、力争所写的东西清晰易懂图文并茂三、尽最大可能确保所写的东西精准有实用价值。 由于我认为你既然要把你的文章发布出来那么你就一定要为你的读者负责。不然就不要发表出来。一切为读者服务。 ok闲不多说。接下来咱们立马进入本文章的主题排序算法。众所周知高速排序算法是排序算法中的重头戏。因此本系列本文就从高速排序開始。------------------------------------------------------一、高速排序算法的基本特性时间复杂度On*lgn最坏On^2空间复杂度On*lgn不稳定。高速排序是一种排序算法对包括n个数的输入数组平均时间为Onlgn最坏情况是On^2。一般是用于排序的最佳选择。由于基于比較的排序最快也仅仅能达到Onlgn。二、高速排序算法的描写叙述算法导论第7章高速排序时基于分治模式处理的对一个典型子数组A[p...r]排序的分治过程为三个步骤1.分解A[p..r]被划分为俩个可能空的子数组A[p ..q-1]和A[q1 ..r]使得A[p ..q-1] A[q] A[q1 ..r]2.解决通过递归调用高速排序对子数组A[p ..q-1]和A[q1 ..r]排序。3.合并。 三、高速排序算法版本号一QUICKSORT(A, p, r)1 if p r2 then q ← PARTITION(A, p, r) //关键3 QUICKSORT(A, p, q - 1)4 QUICKSORT(A, q 1, r)数组划分高速排序算法的关键是PARTITION过程它对A[p..r]进行就地重排PARTITION(A, p, r)1 x ← A[r]2 i ← p - 13 for j ← p to r - 14 do if A[j] ≤ x5 then i ← i 16 exchange A[i] - A[j]7 exchange A[i 1] - A[r]8 return i 1 ok咱们来举一个详细而完整的样例。来对下面数组进行高速排序 2 8 7 1 3 5 6 4(主元)一、i p/j 2 8 7 1 3 5 6 4(主元)j指的24于是ii也指到22和2互换原数组不变。j后移直到指向1..二、 j指向14于是ii指向了8所以8与1交换。数组变成了 i j 2 1 7 8 3 5 6 4三、j后移指向了3,34于是ii这是指向了7于是7与3交换。数组变成了 i j 2 1 3 8 7 5 6 4四、j继续后移发现没有再比4小的数所以执行到了最后一步即上述PARTITION(A, p, r)代码部分的 第7行。因此i后移一个单位指向了8 i j 2 1 3 8 7 5 6 4A[i 1] - A[r]即8与4交换所以数组终于变成了例如以下形式 2 1 3 4 7 5 6 8ok高速排序第一趟完毕。4把整个数组分成了俩部分2 1 3,7 5 6 8再递归对这俩部分分别高速排序。i p/j 2 1 3(主元) 2与2互换不变然后又是1与1互换还是不变最后3与3互换不变终于3把2 1 3分成了俩部分2 1和3.再对2 1递归排序终于结果成为了1 2 3.7 5 6 8(主元)7、5、6、都比8小所以第一趟还是7 5 6 8只是此刻8把7 5 6 8分成了 7 5 6和8.[7 5 6-5 7 6-5 6 7]再对7 5 6递归排序终于结果变成5 6 7 8。ok全部过程全部分析完毕。最后看下我画的图 高速排序算法版本号二只是这个版本号不再选取如上第一版本号的数组的最后一个元素为主元而是选择数组中的第一个元素为主元。/**************************************************//* 函数功能高速排序算法 *//* 函数參数结构类型table的指针变量tab *//* 整型变量left和right左右边界的下标 *//* 函数返回值空 *//* 文件名称quicsort.c 函数名quicksort () *//**************************************************/void quicksort(table *tab,int left,int right){ int i,j; if(leftright) { ileft;jright; tab-r[0]tab-r[i]; //准备以本次最左边的元素值为标准进行划分先保存其值 do { while(tab-r[j].keytab-r[0].keyij) j--; //从右向左找第1个小于标准值的位置j if(ij) //找到了位置为j { tab-r[i].keytab-r[j].key;i; } //将第j个元素置于左端并重置i while(tab-r[i].keytab-r[0].keyij) i; //从左向右找第1个大于标准值的位置i if(ij) //找到了位置为i { tab-r[j].keytab-r[i].key;j--; } //将第i个元素置于右端并重置j }while(i!j); tab-r[i]tab-r[0]; //将标准值放入它的终于位置,本次划分结束 quicksort(tab,left,i-1); //对标准值左半部递归调用本函数 quicksort(tab,i1,right); //对标准值右半部递归调用本函数 }}----------------ok咱们还是以上述相同的数组应用此快排算法的版本号二来演示此排序过程这次以数组中的第一个元素2为主元。 2(主) 8 7 1 3 5 6 4请细看 2 8 7 1 3 5 6 4 i- -j (找大) (找小)一、jj找第一个小于2的元素1,1赋给(覆盖重置)i所指元素2得到 1 8 7 3 5 6 4 i j 二、ii找到第一个大于2的元素8,8赋给(覆盖重置)j所指元素(NULL-8) 1 7 8 3 5 6 4 i -j三、jj继续左移在与i碰头之前没有找到比2小的元素结束。最后主元2补上。第一趟快排结束之后数组变成 1 2 7 8 3 5 6 4第二趟 7 8 3 5 6 4 i- -j (找大) (找小) 一、jj找到4比主元7小4赋给7所处位置得到 4 8 3 5 6 i- j二、ii找比7大的第一个元素8,8覆盖j所指元素(NULL) 4 3 5 6 8 i j 4 6 3 5 8 i- j i与j碰头结束。第三趟 4 6 3 5 7 8......下面分析原理一致略过。最后的结果例如以下图所看到的 1 2 3 4 5 6 7 8相信经过以上内容的详细分析你一定明了了。最后贴一下我画的关于这个排序过程的图 完。一月五日补充。OK,上述俩种算法明确一种就可以。------------------------------------------------------------- 五、高速排序的最坏情况和最快情况。最坏情况发生在划分过程产生的俩个区域分别包括n-1个元素和一个0元素的时候即假设算法每一次递归调用过程中都出现了这样的划分不正确称。那么划分的代价为On由于对一个大小为0的数组递归调用后返回T0O1。估算法的执行时间能够递归的表示为 TnTn-1T0On)T(n-1)O(n). 能够证明为TnOn^2。因此假设在算法的每一层递归上划分都是最大程度不正确称的那么算法的执行时间就是On^2。亦即高速排序算法的最坏情况并不比插入排序的更好。此外当数组全然排好序之后高速排序的执行时间为On^2。而在相同情况下插入排序的执行时间为On。//注请注意理解这句话。我们说一个排序的时间复杂度是仅仅针对一个元素的。//意思是把一个元素进行插入排序即把它插入到有序的序列里花的时间为n。 再来证明最快情况下即PARTITION可能做的最平衡的划分中得到的每一个子问题都不能大于n/2.由于当中一个子问题的大小为|_n/2_|。还有一个子问题的大小为|-n/2-|-1.在这样的情况下高速排序的速度要快得多。为 T(n)2Tn/2On.能够证得TnOnlgn。直观上看高速排序就是一颗递归数当中PARTITION总是产生9:1的划分总的执行时间为Onlgn。各结点中示出了子问题的规模。每一层的代价在右边显示。每一层包括一个常数c。完。July、二零一一年一月四日。请各位自行思考下面这个版本号相应于上文哪个版本号? HOARE-PARTITION(A, p, r) 1 x ← A[p] 2 i ← p - 1 3 j ← r 1 4 while TRUE 5 do repeat j ← j - 1 6 until A[j] ≤ x 7 repeat i ← i 1 8 until A[i] ≥ x 9 if i j10 then exchange A[i] ↔ A[j]11 else return j 我经常思考为什么有的人当时明明读懂明确了一个算法而一段时间过后它又对此算法全然陌生而不了解了列? 我想究其根本还是没有彻底明确此高速排序算法的原理与来龙去脉...那作何改进列仅仅能找发明那个算法的原作者了从原作者身上再多挖掘点实用的东西出来。 July、二零一一年二月十五日更新。最后再给出一个高速排序算法的简洁演示样例 Quicksort函数void quicksort(int l, int u){ int i, m; if (l u) return; swap(l, randint(l, u)); m l; for (i l1; i u; i) if (x[i] x[l]) swap(m, i); swap(l, m); quicksort(l, m-1); quicksort(m1, u);} 假设函数的调用形式是quicksort(0, n-1)那么这段代码将对一个全局数组x[n]进行排序。函数的两个參数各自是将要进行排序的子数组的下标l是较低的下标而u是较高的下标。 函数调用swap(i,j)将会交换x[i]与x[j]这两个元素。第一次交换操作将会依照均匀分布的方式在l和u之间随机地选择一个划分元素。 ok很多其它请參考我写的关于高速排序算法的第二篇文章一之续、高速排序算法的深入分析第三篇文章十二、一之再续高速排序算法之全部版本号的c/c实现。 July、二零一一年二月二十日更新。 转载于:https://www.cnblogs.com/gcczhongduan/p/4505448.html
