快速排序過程詳解

快速排序是基于交換思想對冒泡排序的一種改進的交換排序方法，稱為分區交換排序。快速排序的核心是劃分，可以用遞歸來實作。

該段代碼摘自《大話資料結構》：

L->length（序列長度） L（序列） pivot（樞軸值）

由于要用到遞歸，将排序算法封裝起來。

void QuickSort(Sqlist *L)
{

    Qsort(L,1,L->length);

}
void Qsort(Sqlist *L,int low,int high)
{
   int pivot;
   if(low<high)
   {
       //算樞軸值
    pivot=Partition(L,low,high);

    Qsort(L,low,pivot-1);  //對低子表遞歸排序
    Qsort(L,pivot+1,hign); //對高子表遞歸排序
   }
}

int Partition(Sqlist *L,int low,int high)
{
    int pivotkey;

    pivotkey=L->r[low];  //用子表的第一個記錄作樞軸記錄

    while(low<high)
    {
        while(low<high&&L->r[high]>=pivotkey)
            high--;
        swap(L,low,high);
        while(low<high&&L->r[low]<=pivotkey)
            low++;
        swap(L,low,high);
    }
}
           

以下給出一個比較完整的将數組排成基本有序的過程：

下面是實作基本有序的一個小練習：

Partition函數的功能就是 将序列分區，使其實作基本有序，然後傳回樞軸值在序列中的位置。

時間複雜度

1. 快速排序的平均時間複雜度是 O(nlogn)。

2.最壞情況下時間複雜度是O(n^2)。（冒泡）