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

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

     快速排序算法過程分為如下幾步：

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

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

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

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

     看完這四步，我相信很多人又要開始退縮了，這里面又有遞歸，其實不用怕，仔細(xì)分析一下先，快速排序和歸并排序挺像的，可以看出來這是一個思想的延伸，不同的是歸并排序在遞歸（排序）之前并不對數(shù)列進(jìn)行任何處理，而快速排序是要進(jìn)行一些排序的預(yù)處理，得到兩個子序列，然后再將這兩個子序列進(jìn)行排序。在這里面要特別提到的一個就是如何選取p值對于這個算法的效率是有影響的，這也是快速排序很微妙的一個事情，基本思想說完了，慣例是貼個代碼了。

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); 
} 

     ***個函數(shù)你可以理解為一個驅(qū)動程序，為的是隱藏一些實現(xiàn)細(xì)節(jié)，讓調(diào)用者調(diào)用時傳遞更少的參數(shù)，減小出錯的可能性，這也是一種有技巧的設(shè)計方法。第二個函數(shù)是真正的快速排序函數(shù)，從代碼上看，這里選取每個序列的***個點作為p點，然后分別從兩端開始和這個p點進(jìn)行比較，先從右端一直找到***個小于p點的值，然后停住，交換左端左邊現(xiàn)在掃描到的值（也就是p點的值），兩個值，然后換從左邊開始掃描，找到目前比p點大值，交換，如此繼續(xù)，***當(dāng)從左端掃描的坐標(biāo)和右端掃描的坐標(biāo)相遇時，記下這個點，將p點和這個點的值交換，這樣就可以保證p點左邊的值都是比p點的值?。ǖ遣灰欢ㄊ怯行虻模?，右邊的值都比p點的值要大，如此循環(huán)，然后依次對兩個子序列進(jìn)行一樣的排序過程，因為在上一篇里我已經(jīng)詳細(xì)的分析了遞歸的調(diào)用過程，所以在這里我就不再分析了，唉，人還是懶的。

     先看下效果好了。

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

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

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

【編輯推薦】