七、騷年，這就是你的***速度了嗎？

      在介紹了前面的幾個(gè)排序算法之后，這一次我準(zhǔn)備寫(xiě)寫(xiě)快速排序，快速排序之所以叫快速排序是因?yàn)樗芸?，它是已知?shí)踐中最快的排序算法（不過(guò)曾經(jīng)我看過(guò)一個(gè)叫g(shù)oogle的位圖排序算法，傳說(shuō)能更快，但從那以后我再也沒(méi)有找到過(guò)相關(guān)的資料了，所以說(shuō)江湖小報(bào)上的消息還是不要信的比較好），它的平均運(yùn)行時(shí)間能達(dá)到O（NLOGN），而且在絕大部分情況下很容易達(dá)到這個(gè)時(shí)間界。

     快速排序算法過(guò)程分為如下幾步：

     1.如果數(shù)列中的元素只有0個(gè)或者1個(gè)，那么算法結(jié)束，

     2.在待排序數(shù)列中任意選取一個(gè)數(shù)，記為p好了，

     3.將剩下的元素劃分成兩個(gè)子序列，一個(gè)子序列里面的數(shù)全部比p小，另一個(gè)全部比p大，

     4.分別對(duì)兩個(gè)子序列進(jìn)行上述過(guò)程的排序。

     看完這四步，我相信很多人又要開(kāi)始退縮了，這里面又有遞歸，其實(shí)不用怕，仔細(xì)分析一下先，快速排序和歸并排序挺像的，可以看出來(lái)這是一個(gè)思想的延伸，不同的是歸并排序在遞歸（排序）之前并不對(duì)數(shù)列進(jìn)行任何處理，而快速排序是要進(jìn)行一些排序的預(yù)處理，得到兩個(gè)子序列，然后再將這兩個(gè)子序列進(jìn)行排序。在這里面要特別提到的一個(gè)就是如何選取p值對(duì)于這個(gè)算法的效率是有影響的，這也是快速排序很微妙的一個(gè)事情，基本思想說(shuō)完了，慣例是貼個(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)，然后分別從兩端開(kāi)始和這個(gè)p點(diǎn)進(jìn)行比較，先從右端一直找到***個(gè)小于p點(diǎn)的值，然后停住，交換左端左邊現(xiàn)在掃描到的值（也就是p點(diǎn)的值），兩個(gè)值，然后換從左邊開(kāi)始掃描，找到目前比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)的值?。ǖ遣灰欢ㄊ怯行虻模?，右邊的值都比p點(diǎn)的值要大，如此循環(huán)，然后依次對(duì)兩個(gè)子序列進(jìn)行一樣的排序過(guò)程，因?yàn)樵谏弦黄镂乙呀?jīng)詳細(xì)的分析了遞歸的調(diào)用過(guò)程，所以在這里我就不再分析了，唉，人還是懶的。

     先看下效果好了。

     分析下結(jié)果好了，就看***行，***行里面我們選取的p是34，那么從右端開(kāi)始，81大于34，不用交換，繼續(xù)掃描，12小于34，交換兩個(gè)值，12交換到***位，34交換到倒數(shù)第二位，現(xiàn)在換從左邊掃描，43大于34，又開(kāi)始交換，43變到倒數(shù)第二位，34交換到第二位，如此往復(fù)，得到以34為分界點(diǎn)的，左邊的序列的元素全部比34小，右邊的元素全部比34大。

     下面來(lái)簡(jiǎn)單說(shuō)明一下為什么p點(diǎn)的選取對(duì)于快速排序的效率有一定的影響，因?yàn)榭吹降谌?，是要將序列劃分成為兩個(gè)序列然后進(jìn)行遞歸，試想如果一個(gè)逆序的數(shù)列，也就是54321這種，如果按照我們上述的方法選取p點(diǎn)，會(huì)出現(xiàn)的問(wèn)題就是劃分成了的兩個(gè)子序列，一個(gè)子序列里面是原數(shù)列的所有數(shù)，一個(gè)子序列里面沒(méi)有數(shù)，這樣會(huì)導(dǎo)致效率的大大降低。那么如果是隨機(jī)選取p點(diǎn)呢？這樣會(huì)減少我上面說(shuō)的這個(gè)問(wèn)題，但是會(huì)帶來(lái)的負(fù)面效應(yīng)就是隨機(jī)數(shù)的生成也是要耗費(fèi)大量時(shí)間的，所以說(shuō)這也是一種得不償失的方法。那么有沒(méi)有好一點(diǎn)的方法呢？有一種通用的方法叫做三中值分割法，如果讓快速排序效率盡量高，那么我們的選取的p值盡量是中值，這樣的話分成的兩個(gè)序列比較平均，其實(shí)就是對(duì)于一個(gè)帶排列的數(shù)列，選取其中間位置上的那個(gè)元素，在實(shí)踐中，因?yàn)榇蟛糠謶?yīng)用背景的關(guān)系，所以這樣的方法往往能神奇的提高效率。

原文鏈接：http://www.cnblogs.com/ZXYloveFR/archive/2012/09/27/2705463.html

【編輯推薦】