快速排序由C. A. R. Hoare在1962年提出劫映。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小涤妒，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序搔扁，整個(gè)排序過(guò)程可以遞歸進(jìn)行渣触，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列羡棵。
設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)嗅钻，然后將所有比它小的數(shù)都放到它前面皂冰，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱(chēng)為一趟快速排序养篓。值得注意的是秃流，快速排序不是一種穩(wěn)定的排序算法，也就是說(shuō)柳弄，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)舶胀。詳細(xì)算法實(shí)現(xiàn)如下：
void sort(int a[],intleft,intright)
{
if(left >= right)/*如果左邊索引大于或者等于右邊的索引就代表已經(jīng)整理完成一個(gè)組了*/
{
return;
}
int i = left;
int j = right;
int key = a[left];
while(i < j)/*控制在當(dāng)組內(nèi)尋找一遍*/
{
while(i < j && key <= a[j])
/*而尋找結(jié)束的條件就是概说，1，找到一個(gè)小于或者大于key的數(shù)（大于或小于取決于你想升序還是降序）2嚣伐，沒(méi)有符合條件1的糖赔，并且i與j的大小沒(méi)有反轉(zhuǎn)*/
{
j--;/*向前尋找*/
}
a[i] = a[j];
/*找到一個(gè)這樣的數(shù)后就把它賦給前面的被拿走的i的值（如果第一次循環(huán)且key是a[left]，那么就是給key）*/
while(i < j && key >= a[i])
/*這是i在當(dāng)組內(nèi)向前尋找轩端，同上放典，不過(guò)注意與key的大小關(guān)系停止循環(huán)和上面相反，
因?yàn)榕判蛩枷胧前褦?shù)往兩邊扔基茵，所以左右兩邊的數(shù)大小與key的關(guān)系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*當(dāng)在當(dāng)組內(nèi)找完一遍以后就把中間數(shù)key回歸*/
sort(a, left, i - 1);/*最后用同樣的方式對(duì)分出來(lái)的左邊的小組進(jìn)行同上的做法*/
sort(a, i + 1, right);/*用同樣的方式對(duì)分出來(lái)的右邊的小組進(jìn)行同上的做法*/
/*當(dāng)然最后可能會(huì)出現(xiàn)很多分左右奋构，直到每一組的i = j 為止*/
}
如果待排序序列是絕對(duì)隨機(jī)，快排是排序速度最快的排序方式拱层，平均時(shí)間復(fù)雜度：O（nlgn）弥臼，最壞：O（n^2），空間復(fù)雜度：O（nlgn）根灯。
