快速排序是分治策略喷屋、迭代的典型示例苏研，需要熟練掌握。
核心思想
將數(shù)組中所有元素都跟一個基準元素x比（隨意選取欲诺，常取第一個或最后一個）抄谐，比x小的劃分成左邊一塊，比x大的劃分成右邊一塊扰法，得到兩個子問題蛹含。然后遞歸處理這兩個子問題即可。
其關鍵在于對數(shù)組的劃分塞颁。
代碼實現(xiàn)
下面是C++實現(xiàn)代碼：
代碼參考：常用算法之----快速排序
#include <iostream>
using namespace std;
//數(shù)組打印
void P(int a[],int n)
{
for(int i=0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
}
int quickSortPartition(int s[], int l, int r){
//Swap(s[l], s[(l + r) / 2]); //若以中間數(shù)為基準浦箱，則先將中間的這個數(shù)和第一個數(shù)交換即可
int i = l, j = r, x = s[l]; //將最左元素記錄到x中
while (i < j)
{
// 從右向左找第一個<x的數(shù)
// 無需考慮下標越界
while(i < j && s[j] >= x)
j--;
if(i < j)
s[i++] = s[j]; //直接替換掉最左元素（已在x中存有備份）
// 從左向右找第一個>x的數(shù)
while(i < j && s[i] <= x)
i++;
if(i < j)
//替換掉最右元素(已在最左元素中有備份）
//最左元素一定被覆蓋過，若沒有殴边，則表明右側所有元素都>x憎茂，那么算法將終止
s[j--] = s[i];
}
s[i] = x; //i的位置放了x珍语，所以其左側都小于x锤岸，右側y都大于x
return i;
}
void quickSort(int s[], int l, int r)
{
//數(shù)組左界<右界才有意義，否則說明都已排好板乙，直接返回即可
if (l>=r){
return;
}
// 劃分是偷，返回基準點位置
int i = quickSortPartition(s, l, r);
// 遞歸處理左右兩部分，i處為分界點募逞，不用管i了
quickSort(s, l, i - 1);
quickSort(s, i + 1, r);
}
int main()
{
int a[]= {72,6,57,88,60,42,83,73,48,85};
//int a[]= {10,9,8,7,6,5,4,3,2,1};
P(a,10);
quickSort(a,0,9);//注意最后一個參數(shù)是n-1
P(a,10);
return 0;
}
這個版本算法的優(yōu)點是蛋铆，不用將某兩個元素互換，一次移動直接將留有備份的元素覆蓋放接。其實刺啦，從兩頭交替掃描就是為了一次挪一個，騰出來坑后再填下一個纠脾。
也可以從一頭單向掃描玛瘸，那時就需要交換倆元素位置。（參考《算法導論》第2版第七章快速排序）
復雜度分析
以比較運算作為基本運算糊渊，衡量其時間復雜度T(n)。
由于每次將原問題劃分成兩個規(guī)模減半的子問題慧脱，劃分的額外工作量為O(n)渺绒，所以其遞推公式為：
T(n) = 2 * T(n/2) + O(n)
T(1) = 0
根據(jù)主定理（或迭代、或遞歸樹）可得，T(n) = O( nlog(n) )宗兼。（算法復雜度中的log默認指以2為底的log2）
快排為什么快（分治策略好在哪）
相比之下躏鱼，選擇排序、插入排序殷绍、冒泡排序等的時間復雜度均為O(n^2)挠他。為什么采用分治策略的快速排序能將復雜度大大減小呢？分成兩個子問題后節(jié)省了哪些時間呢篡帕？
因為劃分后殖侵，兩個子問題之間存在某種關系，這些信息節(jié)省了后續(xù)處理時間镰烧。
以快速排序算法為例拢军，數(shù)組中所有元素都跟基準元素x比較后，比x小的劃分成左邊一塊怔鳖，比x大的劃分成右邊一塊茉唉。
這樣，雖然左右兩部分元素沒有直接對比（都只和x做了對比）结执，但已經(jīng)可以知道度陆，x左側的所有元素都小于右側的。
一趟對比下來献幔，每個元素不僅確定了和x的大小關系懂傀，還有了較大、較小之分蜡感。這就比蠻力兩兩對比（比如選擇排序蹬蚁、插入排序、冒泡排序）節(jié)省了時間郑兴。
擴展資料：十大經(jīng)典排序算法（動圖演示）
