快速排序算法（6）

目錄

​​快速排序算法原理​​

​​快速排序算法的使用場景​​

​​快速排序算法的實作​​

​​快速排序算法的運作結果​​

快速排序算法原理

      快速排序算法首先會在序列中随機選擇一個基準值（pivot），然後将除了基準值以外的數分為“比基準值小的數”和“比基準值大的數”這兩個類别，再将其排列成以下形式。分割子序列時需要選擇基準值，如果每次選擇的基準值都能使得兩個子序列的長度為原本的一半，那麼快速排序的運作時間和歸并排序的一樣，都為O（nlogn）。和歸并排序類似，将序列對半分割log2n次之後，子序列裡便隻剩下一個資料，這時子序列的排序也就完成了。是以，如果像下圖這樣一行行地展現根據基準值分割序列的過程，那麼總共會有log2n行分割子序列時需要選擇基準值，如果每次選擇的基準值都能使得兩個子序列的長度為原本的一半，那麼快速排序的運作時間和歸并排序的一樣，都為O（nlogn）。和歸并排序類似，将序列對半分割log2n次之後，子序列裡便隻剩下一個資料，這時子序列的排序也就完成了。是以，如果像下圖這樣一行行地展現根據基準值分割序列的過程，那麼總共會有log2n行。

快速排序算法的使用場景

快速排序算法的實作

void QuickSort(int *a, int left, int right)
{
    int i = left;
    int j = right;
    int key = a[left];

    if(left >= right)
        return;

    Printf("Sort before:", a, right+1);
    printf("left=%d, right=%d, KeyValue=%d\n", left, right, key);
    printf("\n\n");
     
    while(i < j)  
    {
        while(i < j && key <= a[j])
            j--;
         
        a[i] = a[j];
         
        while(i < j && key >= a[i])
            i++;
         
        a[j] = a[i];
    }
     
    a[i] = key;
    QuickSort(a, left, i-1);
    Printf("Sort after1:", a, right+1);
    printf("\n\n");
    QuickSort(a, i+1, right);
    Printf("Sort after2:", a, right+1);
    printf("\n\n");


}

int main(int argc, char *argv[])
{
    int iArray[] ={10, 23, 65, -101, 10000, 999};
    int *piArryTmp;

    QuickSort(iArray, 0, sizeof(iArray)/sizeof(iArray[0])-1);

    system("pause");
    return 0;
}      

快速排序算法的運作結果

Sort before:
10 23 65 -101 10000 999
left=0, right=5, KeyValue=10


Sort after1:
-101 10 65 23 10000 999


Sort before:
-101 10 65 23 10000 999
left=2, right=5, KeyValue=65


Sort after1:
-101 10 23 65 10000 999


Sort before:
-101 10 23 65 10000 999
left=4, right=5, KeyValue=10000


Sort after1:
-101 10 23 65 999 10000


Sort after2:
-101 10 23 65 999 10000


Sort after2:
-101 10 23 65 999 10000


Sort after2:
-101 10 23 65 999 10000


Press any key to continue . . .