建站
咨詢
售后
建站咨詢
新聞中心
七、騷年，這就是你的***速度了嗎？
創(chuàng)新互聯(lián)作為成都網(wǎng)站建設(shè)公司，專注成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)，有關(guān)企業(yè)網(wǎng)站制作方案、改版、費(fèi)用等問題，行業(yè)涉及成都工商代辦等多個(gè)領(lǐng)域，已為上千家企業(yè)服務(wù)，得到了客戶的尊重與認(rèn)可。
在介紹了前面的幾個(gè)排序算法之后，這一次我準(zhǔn)備寫寫快速排序，快速排序之所以叫快速排序是因?yàn)樗芸?，它是已知?shí)踐中最快的排序算法（不過曾經(jīng)我看過一個(gè)叫g(shù)oogle的位圖排序算法，傳說能更快，但從那以后我再也沒有找到過相關(guān)的資料了，所以說江湖小報(bào)上的消息還是不要信的比較好），它的平均運(yùn)行時(shí)間能達(dá)到O（NLOGN），而且在絕大部分情況下很容易達(dá)到這個(gè)時(shí)間界。
快速排序算法過程分為如下幾步：
1.如果數(shù)列中的元素只有0個(gè)或者1個(gè)，那么算法結(jié)束，
2.在待排序數(shù)列中任意選取一個(gè)數(shù)，記為p好了，
3.將剩下的元素劃分成兩個(gè)子序列，一個(gè)子序列里面的數(shù)全部比p小，另一個(gè)全部比p大，
4.分別對(duì)兩個(gè)子序列進(jìn)行上述過程的排序。
看完這四步，我相信很多人又要開始退縮了，這里面又有遞歸，其實(shí)不用怕，仔細(xì)分析一下先，快速排序和歸并排序挺像的，可以看出來這是一個(gè)思想的延伸，不同的是歸并排序在遞歸（排序）之前并不對(duì)數(shù)列進(jìn)行任何處理，而快速排序是要進(jìn)行一些排序的預(yù)處理，得到兩個(gè)子序列，然后再將這兩個(gè)子序列進(jìn)行排序。在這里面要特別提到的一個(gè)就是如何選取p值對(duì)于這個(gè)算法的效率是有影響的，這也是快速排序很微妙的一個(gè)事情，基本思想說完了，慣例是貼個(gè)代碼了。
- void quickSort(int numbers[], int array_size)
- {
- q_sort(numbers, 0, array_size - 1);
- }
- void q_sort(int numbers[], int left, int right)
- {
- int pivot, l_hold, r_hold;
- l_hold = left;
- r_hold = right;
- pivot = numbers[left];
- while (left < right)
- {
- while ((numbers[right] >= pivot) && (left < right))
- right--;
- if (left != right)
- {
- numbers[left] = numbers[right];
- left++;
- }
- while ((numbers[left] <= pivot) && (left < right))
- left++;
- if (left != right)
- {
- numbers[right] = numbers[left];
- right--;
- }
- }
- numbers[left] = pivot;
- pivot = left;
- left = l_hold;
- right = r_hold;
- if (left < pivot)
- q_sort(numbers, left, pivot-1);
- if (right > pivot)
- q_sort(numbers, pivot+1, right);
- }
***個(gè)函數(shù)你可以理解為一個(gè)驅(qū)動(dòng)程序，為的是隱藏一些實(shí)現(xiàn)細(xì)節(jié)，讓調(diào)用者調(diào)用時(shí)傳遞更少的參數(shù)，減小出錯(cuò)的可能性，這也是一種有技巧的設(shè)計(jì)方法。第二個(gè)函數(shù)是真正的快速排序函數(shù)，從代碼上看，這里選取每個(gè)序列的***個(gè)點(diǎn)作為p點(diǎn)，然后分別從兩端開始和這個(gè)p點(diǎn)進(jìn)行比較，先從右端一直找到***個(gè)小于p點(diǎn)的值，然后停住，交換左端左邊現(xiàn)在掃描到的值（也就是p點(diǎn)的值），兩個(gè)值，然后換從左邊開始掃描，找到目前比p點(diǎn)大值，交換，如此繼續(xù)，***當(dāng)從左端掃描的坐標(biāo)和右端掃描的坐標(biāo)相遇時(shí)，記下這個(gè)點(diǎn)，將p點(diǎn)和這個(gè)點(diǎn)的值交換，這樣就可以保證p點(diǎn)左邊的值都是比p點(diǎn)的值?。ǖ遣灰欢ㄊ怯行虻模疫叺闹刀急萷點(diǎn)的值要大，如此循環(huán)，然后依次對(duì)兩個(gè)子序列進(jìn)行一樣的排序過程，因?yàn)樵谏弦黄镂乙呀?jīng)詳細(xì)的分析了遞歸的調(diào)用過程，所以在這里我就不再分析了，唉，人還是懶的。
先看下效果好了。
分析下結(jié)果好了，就看***行，***行里面我們選取的p是34，那么從右端開始，81大于34，不用交換，繼續(xù)掃描，12小于34，交換兩個(gè)值，12交換到***位，34交換到倒數(shù)第二位，現(xiàn)在換從左邊掃描，43大于34，又開始交換，43變到倒數(shù)第二位，34交換到第二位，如此往復(fù)，得到以34為分界點(diǎn)的，左邊的序列的元素全部比34小，右邊的元素全部比34大。
下面來簡(jiǎn)單說明一下為什么p點(diǎn)的選取對(duì)于快速排序的效率有一定的影響，因?yàn)榭吹降谌?，是要將序列劃分成為兩個(gè)序列然后進(jìn)行遞歸，試想如果一個(gè)逆序的數(shù)列，也就是54321這種，如果按照我們上述的方法選取p點(diǎn)，會(huì)出現(xiàn)的問題就是劃分成了的兩個(gè)子序列，一個(gè)子序列里面是原數(shù)列的所有數(shù)，一個(gè)子序列里面沒有數(shù)，這樣會(huì)導(dǎo)致效率的大大降低。那么如果是隨機(jī)選取p點(diǎn)呢？這樣會(huì)減少我上面說的這個(gè)問題，但是會(huì)帶來的負(fù)面效應(yīng)就是隨機(jī)數(shù)的生成也是要耗費(fèi)大量時(shí)間的，所以說這也是一種得不償失的方法。那么有沒有好一點(diǎn)的方法呢？有一種通用的方法叫做三中值分割法，如果讓快速排序效率盡量高，那么我們的選取的p值盡量是中值，這樣的話分成的兩個(gè)序列比較平均，其實(shí)就是對(duì)于一個(gè)帶排列的數(shù)列，選取其中間位置上的那個(gè)元素，在實(shí)踐中，因?yàn)榇蟛糠謶?yīng)用背景的關(guān)系，所以這樣的方法往往能神奇的提高效率。
當(dāng)前題目：你所能用到的數(shù)據(jù)結(jié)構(gòu)（五）
標(biāo)題URL：http://www.dlmjj.cn/article/dppioho.html
