快速排序(Quick Sort)使用分治法策略愧旦。
它的基本思想是：選擇一個基準(zhǔn)數(shù)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分定罢；其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小笤虫。然后，再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序祖凫，整個排序過程可以遞歸進(jìn)行琼蚯，以此達(dá)到整個數(shù)據(jù)變成有序序列。
快速排序流程：
(1) 從數(shù)列中挑出一個基準(zhǔn)值惠况。
(2) 將所有比基準(zhǔn)值小的擺放在基準(zhǔn)前面遭庶，所有比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)；在這個分區(qū)退出之后稠屠，該基準(zhǔn)就處于數(shù)列的中間位置峦睡。
(3) 遞歸地把"基準(zhǔn)值前面的子數(shù)列"和"基準(zhǔn)值后面的子數(shù)列"進(jìn)行排序。
int main(void)
{
int arr[7]={10,20,36,24,55,34,23};
int n=7;
int l=0;
int r=6;
quick_sort(arr,l,r);
int i=0;
for(i=0;i<n;i++){
printf("%d ",arr[i]);
}
return 0;
}
void quick_sort(int arr[],int l,int r){
if(l<r){
int i=0;
int j=0;
int x=0;
i=l;
j=r;
x=arr[i];
while(i<j){
while(i<j&&arr[j]>x){
j--;// 從右向左找第一個小于x的數(shù)
}
if(i<j){
arr[i]=arr[j];
i++;
}
while(i<j&&arr[i]<x){
i++; // 從左向右找第一個大于x的數(shù)
}
if(i<j){
arr[j]=arr[i];
j--;
}
}
arr[i]=x;
quick_sort(arr,l,i-1);/* 遞歸調(diào)用 */
quick_sort(arr,i+1,r);
}
}
快速排序的時間復(fù)雜度在最壞情況下是O(N2)权埠，平均的時間復(fù)雜度是O(N*lgN)榨了。
這句話很好理解：假設(shè)被排序的數(shù)列中有N個數(shù)。遍歷一次的時間復(fù)雜度是O(N)攘蔽，需要遍歷多少次呢阻逮？至少lg(N+1)次，最多N次秩彤。
(01) 為什么最少是lg(N+1)次叔扼？快速排序是采用的分治法進(jìn)行遍歷的，我們將它看作一棵二叉樹漫雷，它需要遍歷的次數(shù)就是二叉樹的深度瓜富，而根據(jù)完全二叉樹的定義，它的深度至少是lg(N+1)降盹。因此与柑，快速排序的遍歷次數(shù)最少是lg(N+1)次。
(02) 為什么最多是N次？這個應(yīng)該非常簡單价捧，還是將快速排序看作一棵二叉樹丑念，它的深度最大是N。因此结蟋，快讀排序的遍歷次數(shù)最多是N次脯倚。
