大神的世界

假設有n個數要排序該怎麼做呢?

這裡要介紹的排序法叫做「quick sort」

quick sort 中文翻作 快速排序法

方法: 與基準值做比較

        小於基準值的放左邊

        大於基準值的放右邊

       (此為小到大，大到小相反即可)

首先，以第一個作為基準值 (也可以不用第一個)

自基準值(不含)右側找尋第一個大於它的數

自數列末端(含)左測找尋第一個小於它的數

找到後先判別這兩個位置是否大的在左邊，小的在右邊

(因為要小到大)

是的話  (不合)

交換

重複執行直到兩尋找位置交錯

把基準值與交錯位置的值做交換

此時，我們可以保證

基準值左邊的數必小於它

基準值右邊的數必大於它

我們不確定的是

基準值左邊的數列有沒有排好

基準值右邊的數列有沒有排好

因此把這整個數列切成三段

一段是基準值左邊

一段是基準值本身

一段是基準值右邊

把左右兩邊的數列按照上面步驟重新排序

直到排序完成

時間複雜度

最佳: O(nlogn) 

最差: O(n^2) 

平均: O(nlogn) 

穩定性: 不穩定

程式碼:

#include <iostream>

using namespace std;

//傳值交換沒有用
//傳址交換才有用
void swap(int *a, int *b)
{
    int t = *a;  //t的值 = a位置的值
    *a = *b;     //a位置的值 = b位置的值
    *b = t;      //b位置的值 = t的值
}

//快數排序法
void quicksort(int *arr, int left, int right)
{
    //基準值,左邊找尋位置,右邊找尋位置
    int pivot, i, j;

    //若數列的左端>=右端，甭排了
    if(left >= right) return;

    //基準值設為第1個
    pivot = arr[left];

    //自基準值右側找起
    i = left + 1;
    //自數列末端找起
    j = right;

    while(1)
    {
        //找尋第一個大於基準值的數的位置
        while(i < right)
        {
            if(arr[i] > pivot)
                break;
            i = i+1;
        }

        //找尋第一個小於基準值的數的位置
        while(j > left)
        {
            if(arr[j] < pivot)
                break;
            j = j-1;
        }

        //若兩位置交錯，不用換，也不用找了
        if(i >= j) break;

        //兩位置沒交錯，交換兩數
        swap(&arr[i], &arr[j]);
    }

    //把基準值的數與交錯位置的數做交換

    //此處只能跟j換，因為arr[j] <= pivot
    //若為大到小也一樣只能跟j換，因為arr[j] >= pivot
    swap(&arr[left], &arr[j]);

    //左數列做排序
    quicksort(arr, 0, j-1);
    //右數列做排序
    quicksort(arr, j+1, right);
}

int main()
{
    int arr[100];
    int n;

    while(cin >> n)
    {
        for(int i = 0; i<n; i++)
            cin >> arr[i];

        quicksort(arr, 0, n-1);

        for(int i = 0; i<n; i++)
            cout << arr[i] << " ";
        cout << endl;
    }

    return 0;

}