快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下趁蕊，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較坞生。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見掷伙。事實(shí)上是己，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來任柜。
快速排序使用分治法（Divide and conquer）策略來把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）卒废。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看宙地，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法摔认。
算法步驟：
- 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）;
- 重新排序數(shù)列宅粥，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面参袱，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后秽梅，該基準(zhǔn)就處于數(shù)列的中間位置抹蚀。這個(gè)稱為分區(qū)（partition）操作；
- 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序
時(shí)間復(fù)雜度和空間復(fù)雜度
時(shí)間復(fù)雜度：
(1)最好： O(nlogn）
（2)最壞：O(n2)
(3)平均： O(nlogn）
空間復(fù)雜度：
O（nlogn）
參考代碼
C語(yǔ)言
#include <stdio.h>
int getPivot(int a[],int left, int right){
int i = left,j = right,X = a[i];
while (i<j) {
//先從右往左找,當(dāng)大于基準(zhǔn)數(shù)的時(shí)候企垦，一直往左找
while (i<j && a[j] >= X) {
j--;
}
if (i<j) {
a[i] = a[j];
i++;
}
//從左往右找环壤，當(dāng)小于基準(zhǔn)數(shù)的時(shí)候，一直往右找
while (i<j && a[i] < X) {
i++;
}
if (i<j) {
a[j] = a[i];
j--;
}
}
//將基準(zhǔn)數(shù)插入當(dāng)前下標(biāo)
a[i] = X;
return i;
}
void quiteSort(int a[],int left,int right){
if (left<right) {
int pivot = getPivot(a, left, right);
quiteSort(a, left, pivot-1);
quiteSort(a, pivot+1, right);
}
}
int main(int argc, const char * argv[]) {
int a[] = {7,3,5,6,8,1,9,2,4};
quiteSort(a, 0, 8);
for (int i = 0 ; i<9; i++) {
printf("%d ",a[i]);
}
return 0;
}
