算法步驟：
1：從數(shù)列中挑選一個(gè)元素构捡，稱(chēng)為“基準(zhǔn)”脏里，
2：重新排序數(shù)列果漾，所有元素比基準(zhǔn)小的值擺放在基準(zhǔn)前球切，所有元素比基準(zhǔn)大的值擺放在基準(zhǔn)后，（相同的數(shù)可以任意一邊）在這個(gè)分區(qū)退出之后绒障，該基準(zhǔn)處于分區(qū)的中間位置吨凑。這個(gè)稱(chēng)為分區(qū)操作
3:遞歸的把小于基準(zhǔn)元素的子數(shù)列和大于基準(zhǔn)元素的自數(shù)列進(jìn)行排序
intpartition(int*arr,intlow,inthigh){
intprivot = arr[high];
inti = low - 1;
intj,tmp;
for(j = low; j
if(arr[j]
tmp = arr[++i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
tmp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = tmp;
returni + 1;
}
voidquick_sort(int*arr,intlow,inthigh){
if(low
intmid =partition(arr, low, high);
quick_sort(arr,low,mid-1);
quick_sort(arr,mid + 1,high);
}
}
intmain(intargc,constchar* argv[]) {
intarr[10] = {1,2,5,3,6,8,7,23,15};
quick_sort(arr, 0, 9);
inti;
for(i = 0; i < 10; ++i) {
printf("%d ",arr[i]);
}
return0;
}
算法復(fù)雜度：
最壞情況下的開(kāi)拍時(shí)間復(fù)雜度
最壞的情況發(fā)生在劃分過(guò)程中產(chǎn)生的兩個(gè)區(qū)域分別包含一個(gè)n-1和一個(gè)0元素的時(shí)候，即假設(shè)算法每一次遞歸調(diào)用過(guò)程中都出現(xiàn)了户辱，這種劃分不對(duì)稱(chēng)鸵钝，那么劃分的代價(jià)為o(n)，因?yàn)閷?duì)一個(gè)大小為0的數(shù)組遞歸調(diào)用后庐镐，返回T（0）=O(1)恩商，估算法的運(yùn)行時(shí)間可以遞歸表示為：
T（n）= T(n-1) + T(0) +O(n) = T(n-1)+O(n).
可以證明為T(mén)(n) = O(n^2).
因此，若在算法的每一層遞歸上焚鹊，劃分都是最大不對(duì)稱(chēng)的話痕届，算法的時(shí)間復(fù)雜度為O(n^2)
最快情況下開(kāi)拍時(shí)間復(fù)雜度：
最快情況下，及Partition可能做的最平衡的劃分中末患，得到的每一個(gè)子問(wèn)題都不能大于n/2研叫。因?yàn)槠渲幸粋€(gè)子問(wèn)題的大小為|n/2|。另一個(gè)的子問(wèn)題的大小為|-n/2|-1
在這種情況下璧针，快速排序的速度要快的多
T(n)<2T(n/2)+O(n),可以證得嚷炉，T(n) = O(nlgn)
