本文章只是簡單講解快速排序的原理，并沒有深入進(jìn)行討論

希望這篇文章適合你  :)

快速排序被廣泛認(rèn)為它是解決一般問題的最佳排序算法，它比較適合解決大規(guī)模數(shù)據(jù)的排序。

原理思想：（順序是從小到大）

快速排序首先選取一個(gè)“基準(zhǔn)數(shù)”，通過基準(zhǔn)數(shù)將大于它和小于它的數(shù)無序地放在基準(zhǔn)數(shù)的兩邊

什么叫無序？就是大于基準(zhǔn)數(shù)的所有數(shù)只需要放在它的右邊，這些數(shù)之間不被要求為有序，同樣，小于基準(zhǔn)數(shù)的數(shù)所有只需要放在它的左邊，不被要求其有序

這樣就利用“基準(zhǔn)數(shù)”對整個(gè)原始數(shù)列進(jìn)行了分割成兩部分，然后通過遞歸，用上述同樣的方法選取一個(gè)基準(zhǔn)數(shù)進(jìn)行分割，直至整個(gè)數(shù)列被分割的各部分已不能再被分割

下面進(jìn)行演示，基準(zhǔn)數(shù)用定義一個(gè)變量 pivot 存放，每一部分的分割開始都是選擇low下標(biāo)對應(yīng)的數(shù)

這里演示的就是代碼中 partition函數(shù) 的實(shí)現(xiàn)

開始：（假設(shè)low=0，high=6.  當(dāng)前的low是紅色，high是綠色，pivot是藍(lán)色，被放置好在基準(zhǔn)數(shù)兩邊的數(shù)用藍(lán)色字體表示）

首先，選取基準(zhǔn)數(shù)進(jìn)行分割，選擇low下標(biāo)當(dāng)前的元素5為基準(zhǔn)數(shù)，即pivot = 5

然后將 pivot 與 high 下標(biāo)對應(yīng)的數(shù)進(jìn)行對比

結(jié)果如下：

注意！

在這個(gè)時(shí)候，因 pivot = 5 被交換到 high 的下標(biāo)處

那么接下來的比較就是將pivot與low下標(biāo)當(dāng)前的數(shù)進(jìn)行對比

這里是比low對應(yīng)的數(shù)大，結(jié)果如下：

結(jié)果如下：

這時(shí)候 pivot = 5比 a[low] 小，所以又進(jìn)行a[low] 與 a[high]交換

結(jié)果如下：

注意！

在這個(gè)時(shí)候，因pivot = 5被交換到low的下標(biāo)處

那么接下來的比較就是將pivot與high下標(biāo)當(dāng)前的數(shù)進(jìn)行對比

結(jié)果如下：

同樣進(jìn)行交換，結(jié)果如下：

結(jié)果如下：（low++）

結(jié)果如下：

結(jié)果如下：（high--）

結(jié)果如下：（最終結(jié)果low == high，橙色表示）

到這里，已經(jīng)利用 基準(zhǔn)數(shù)pivot = 5 把這個(gè)數(shù)列分為了兩部分（5 的左邊都是小于它的，右邊都是大于它的）

然后遞歸。用同樣的方法，對分割出來的兩部分用“基準(zhǔn)數(shù)”繼續(xù)進(jìn)行分割

/快排函數(shù)  void sort(int *s, int low, int high)  {      int    pivot;      //if語句的判斷是結(jié)束遞歸的簡單情景，不能缺      if (low < high)      {          // partition 函數(shù)就是利用基準(zhǔn)數(shù)進(jìn)行分割的功能函數(shù)，這個(gè)函數(shù)是重點(diǎn)          pivot = partition(s, low, high);            sort(s, pivot + 1, high);          sort(s, low, pivot - 1);       }  }  partition 函數(shù)代碼：
//這個(gè)函數(shù)就是上面演示的代碼實(shí)現(xiàn)  int partition(int *s, int low, int high)  {      int    pivot;      pivot = s[low];        while (low < high)      {          while (low < high && pivot <= s[high])          {              high--;          }          swap(&s[low], &s[high]);          while (low < high && pivot >= s[low])          {              low++;          }          swap(&s[high], &s[low]);      }      return  low;  }