在前面介紹的排序算法中，最快的排序算法為歸並排序（http://www.linuxidc.com/Linux/2014-11/109824.htm），但是歸並排序有一個缺陷就是排序過程中需要O(N)的額外空間。本文介紹的快速排序算法時一種原地排序算法，所需的額外空間復雜度為O(1)。
堆與堆排序 http://www.linuxidc.com/Linux/2014-09/107318.htm
歸並排序的實現 http://www.linuxidc.com/Linux/2014-09/107316.htm
算法介紹：快速排序其實一種根據需找某個元素的具體位置進行排序的方法。比如所存在如下數組
選擇第一個元素5，找到5最終的位置，即5的左邊的數都小於或者等於5，右邊的數都大於或者等於5.
從"6"開始，可知6大於5，此處停住，從“2”開始2小於5，因此交換6與2的位置，然後接著往下走，將所有小於等於5的都放在左邊，大於等於5的都放在右邊，等到如下所示的數組：
此時的索引在4的位置，然後交換5和4的位置，這樣就保證了左邊的都小於5，右邊的都大於5。
然後再分別對5的左右兩邊重復上述過程即可將數組按升序排列。
算法發復雜度分析：假設每次都從中間將數組分開，且算法的運行時間為T(N)，則依據算法的執行過程可知，找到當前元素的位置需要掃面一遍數組即N次，然後再對此元素兩邊的子數組重復上述操作。為此T(N)=2*T(N/2)+N，解得T(N)=O(NlogN)。
算法實現：
尋找切分點
int sort::partition(int* a, const int low, const int high)
{
int value = a[low];
int i=low;
int j=high+1;
while (1)
{
while(a[++i] < value)
{
if(i == high) break;
}
while(value < a[--j]);
//a[low] == value,因此可以知道j==low時，此判斷條件不成立，可知此時i必大於j，從而整個循環結束。
if(i>=j)
break;
swap(a,i,j);
}
swap(a,low,j);
return j;
}
快速排序：
void sort::quick_sort(int* a, const int low, const int high)
{
if(low >= high)
return;
int loc = partition(a,low,high);
quick_sort(a,low,loc-1);
quick_sort(a,loc+1,high);
}
上述即為快速排序的具體實現。但是對上述算法還有很多的改進之處，比如說對存在大多數重復數據的數組排序，初始切分點的選取等等都可以進行改進。具體的改進如下所示：
對於較小的子數組使用插入排序：
void sort::insert_sort_update(int* a, const int n)
{
for(int i=1; i<n; i++)
{
int j=i;
int temp = a[i];
for(; j>0 && temp < a[j-1]; j--)
{
a[j] = a[j-1];
}
a[j] = temp;
}
}
void sort::quick_sort_update_with_insert_sort(int* a, const int low, const int high)
{
if(high <= low+N)
{
insert_sort_for_update(a,low,high);
return;
}
int loc = partition(a,low,high);
quick_sort_update_with_insert_sort(a,low,loc-1);
quick_sort_update_with_insert_sort(a,loc+1,high);
}
對於含有大多數重復元素的改進：
void sort::quick_sort_update_with_partition(int* a,const int low, const int high)
{
if(low>=high)
return;
int lt = low;
int gt = high;
int value = a[low];
int i=low+1;
while(i<=gt)
{
if(a[i]<value)
{
swap(a,i,lt);
i++;
lt++;
}
else if(a[i] > value)
{
swap(a,i,gt);
gt--;
}
else
{
i++;
}
}
quick_sort_update_with_partition(a,low,lt-1);
quick_sort_update_with_partition(a,gt+1,high);
}
上述博文主要介紹了快速排序算法及其改進。歡迎拍磚
