快排圖示.jpg

快速排序之所比較快，因?yàn)橄啾让芭菖判?，每次排序的時(shí)候設(shè)置一個(gè)基準(zhǔn)點(diǎn)，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的右邊。這樣在每次交換的時(shí)候就不會(huì)像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然就提高了。當(dāng)然在最壞的情況下，仍可能是相鄰的兩個(gè)數(shù)進(jìn)行了交換。

快速排序的最差時(shí)間復(fù)雜度和冒泡排序是一樣的都是O(N2)，
平均時(shí)間復(fù)雜度為O(NlogN)。
快速排序是基于“二分”的思想。

C語(yǔ)言代碼實(shí)現(xiàn)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MaxLen 10

void printArray(int arr[],int length)
{
    for (int i = 0; i<length; i++) {
        printf(" %d",arr[i]);
    }
    printf("\n");
}

void quickSort(int arr[],int left,int right)
{
    static int count;
    int i,j,temp;

   
    if (left<right)
    {

        i = left;
        j = right;
        temp = arr[i];
        count ++;
        printf("\n第%d輪，left=%d,right=%d,temp=%d\n",count,left,right,temp);
        
        while (i<j)
        {
            while (i<j&&arr[j]>temp)
            {
                j--;
            }
            
            if (i<j)
            {
                arr[i] = arr[j];
                i++;
            }
            printArray(arr, MaxLen);
            while (i<j&&arr[i]<temp)
            {
                i++;
            }
            
            if (i<j)
            {
                arr[j] = arr[i];
            }
            printArray(arr, MaxLen);
        }
        
        arr[i] = temp;
        printArray(arr, MaxLen);
        quickSort(arr, left, i-1);
        quickSort(arr, i+1, right);
    }
    else
    {
        return;
    }
}



int main(int argc, const char * argv[]) {
    
    int arr[MaxLen] ;
    srand( (unsigned)time( NULL ) );
    
    for (int i = 0; i<MaxLen; i++)
    {
        arr[i] = rand()%50+1;
    }
    printf("原始數(shù)組：\n");
    printArray(arr, MaxLen);

    quickSort(arr, 0, MaxLen-1);
    printf("快排后數(shù)組：\n");
    printArray(arr, MaxLen);
    return 0;
}

運(yùn)行結(jié)果

原始數(shù)組：
 46 3 11 39 37 24 24 11 13 20

第1輪，left=0,right=9,temp=46
 20 3 11 39 37 24 24 11 13 20
 20 3 11 39 37 24 24 11 13 20
 20 3 11 39 37 24 24 11 13 46

第2輪，left=0,right=8,temp=20
 13 3 11 39 37 24 24 11 13 46
 13 3 11 39 37 24 24 11 39 46
 13 3 11 11 37 24 24 11 39 46
 13 3 11 11 37 24 24 37 39 46
 13 3 11 11 37 24 24 37 39 46
 13 3 11 11 37 24 24 37 39 46
 13 3 11 11 20 24 24 37 39 46

第3輪，left=0,right=3,temp=13
 11 3 11 11 20 24 24 37 39 46
 11 3 11 11 20 24 24 37 39 46
 11 3 11 13 20 24 24 37 39 46

第4輪，left=0,right=2,temp=11
 11 3 11 13 20 24 24 37 39 46
 11 3 11 13 20 24 24 37 39 46
 11 3 11 13 20 24 24 37 39 46

第5輪，left=0,right=1,temp=11
 3 3 11 13 20 24 24 37 39 46
 3 3 11 13 20 24 24 37 39 46
 3 11 11 13 20 24 24 37 39 46

第6輪，left=5,right=8,temp=24
 3 11 11 13 20 24 24 37 39 46
 3 11 11 13 20 24 24 37 39 46
 3 11 11 13 20 24 24 37 39 46

第7輪，left=7,right=8,temp=37
 3 11 11 13 20 24 24 37 39 46
 3 11 11 13 20 24 24 37 39 46
 3 11 11 13 20 24 24 37 39 46
快排后數(shù)組：
 3 11 11 13 20 24 24 37 39 46
Program ended with exit code: 0