這是為什么呢？

快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的。每次排序的時候設(shè)置一個基準(zhǔn)點，將小于等于基準(zhǔn)點的數(shù)全部放到基準(zhǔn)點的左邊，將大于等于基準(zhǔn)點的數(shù)全部放到基準(zhǔn)點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然就提高了。當(dāng)然在最壞的情況下，仍可能是相鄰的兩個數(shù)進(jìn)行了交換。因此快速排序的最差時間復(fù)雜度和冒泡排序是一樣的都是O(N²)，它的平均時間復(fù)雜度為O(NlogN)。其實快速排序是基于一種叫做“二分”的思想。我們后面還會遇到“二分”思想，到時候再聊。先上代碼，如下

#include <stdio.h> 
int a[101],n;//定義全局變量，這兩個變量需要在子函數(shù)中使用 
void quicksort(int left,int right) 
{ 
    int i,j,t,temp; 
    if(left>right) 
       return; 
                                
    temp=a[left]; //temp中存的就是基準(zhǔn)數(shù) 
    i=left; 
    j=right; 
    while(i!=j) 
    { 
                   //順序很重要，要先從右邊開始找 
                   while(a[j]>=temp && i<j) 
                            j--; 
                   //再找右邊的 
                   while(a[i]<=temp && i<j) 
                            i++; 
                   //交換兩個數(shù)在數(shù)組中的位置 
                   if(i<j) 
                   { 
                            t=a[i]; 
                            a[i]=a[j]; 
                            a[j]=t; 
                   } 
    } 
    //最終將基準(zhǔn)數(shù)歸位 
    a[left]=a[i]; 
    a[i]=temp; 
                             
    quicksort(left,i-1);//繼續(xù)處理左邊的，這里是一個遞歸的過程 
    quicksort(i+1,right);//繼續(xù)處理右邊的 ，這里是一個遞歸的過程 
} 
int main() 
{ 
    int i,j,t; 
    //讀入數(shù)據(jù) 
    scanf("%d",&n); 
    for(i=1;i<=n;i++) 
                   scanf("%d",&a[i]); 
    quicksort(1,n); //快速排序調(diào)用 
                             
    //輸出排序后的結(jié)果 
    for(i=1;i<=n;i++) 
        printf("%d ",a[i]); 
    getchar();getchar(); 
    return 0; 
}