手寫玩具 - 快速排序

來回翻閱快速排序相關演算法介紹, 真是感嘆大師們的大智慧 ~ 這里通過練習的角度帶大家手寫個玩具. 一起樂一樂, 當課外作業.

參考

1. quick sort source code

演算法實作的相關策略

大街上的快速排序練習作業偏地都是, 這里也是基于類似的策略去構建.

策略1: 指標代替索引

策略2: 基準策略采用三數取中

基準(軸)策略是快排的核心, 它決定最終的演算法復雜度. 有的篩法策略能保證演算法復雜度穩定在 O(nlogn). 多數工程采用策略都在 O(nlogn) ~ O(n^2) 區間, 但演算法復雜度期望穩定在 O(nlogn). 這里折中選擇了三數取中策略, 對有序陣列有不差的效果表現, 演算法復雜度仍然在 O(nlogn) ~ O(n^2) 區間內.

策略3: 排序演算法多維度混合策略

根據資料量和遞回深度來切換使用, 簡單交換排序, 還是插入排序, 還是堆排序等策略.

策略4: 三路分割

{ 等于 | 小于 | 大于 | 等于 } -> { 小于 | 等于 | 大于 } 用于剔出重復元素. 對于重復資料較多時候效果好.

策略5: 尾遞回

核心代碼

static inline void swap_if_great(int * a, int * b) {
    if (*a > *b)
        swap(a, b);
}

/**
 * low, mid, high 三個未知上資料, 選取他們中間資料作為軸驅
 * mid = low + ((high - low) >> 1)
 */
static inline int quick_pivot(int * low, int * high) {
    int * mid = low + ((high - low) >> 1);

    swap_if_great(mid, high);
    swap_if_great(low, high);
    swap_if_great(mid, low);

    // 此時 *mid < *low < *high
    // low 就是三個位置的中值
    return *low;
}

#define INT_SORT_INSERT    (16)

static inline bool quick_sort_before(int * low, int * high, int depth) {
    ptrdiff_t n = high - low;

    if (n <= INT_SORT_INSERT) {
        switch (n) {
        case 0:
        case 1:
            return true;
        case 2:
            swap_if_great(low, high);
            return true;
        case 3:
            swap_if_great(low, low+1);
            swap_if_great(low, high);
            swap_if_great(low+1, high);
            return true;
        default:
            insert_sort(low, high);
            return true;    
        }
    }

    if (depth <= 0) {
        heap_sort(low, n);
        return true;
    }

    return false;
}

static void quick_sort_partial(int * low, int * high, int depth) {
    if (quick_sort_before(low, high, depth))
        return;

    // 開始 quick sort pivot 分割
    int pivot = quick_pivot(low, high);

    // 嘗試三路分割 { 等于 | 小于 | 大于 | 等于 | } -> { 小于 | 等于 | 大于 }
    //
    // --------------------------------------
    // | 等于 | 小于 | ... | 大于 | 等于 |
    // +      +      +     +      +      +
    // low    p      i     j      q      high
    // --------------------------------------
    //
    // -------------------------
    // | 小于 | 等于 | 大于 |
    // +      +      +      +
    // low    i      j      high
    // -------------------------
    //
    // p 指向序列左邊等于 pivot 元素的位置
    // q 指向序列右邊等于 pivot 元素的位置
    // i 指向從左到右掃描的元素位置
    // j 指向從右往左掃描的元素位置
    //
    // 
    int * p = low, * q = high, * i = low, * j = high;
    do {
        while (i < j && *j >= pivot) {
            // 找到與錨點相等的元素, 于是交換到 q 所指向的位置
            if (*j == pivot) 
                swap(j, q--);
            j--;
        }
        *i = *j;

        while (i < j && *i <= pivot) {
            // 找到與錨點相等的元素, 于是交換到 q 所指向的位置 
            if (*i == pivot)
                swap(i, p++);
            i++;
        }
        *j = *i;
    } while (i < j);
    *i = pivot;

    print(low, high - low + 1);

    // 開始處理兩邊重復元素, 將其交換到序列中間
    if (i == p)
        i = low - 1;
    else {
        i--;
        while (--p >= low) 
            swap(i--, p);
    }
    if (j == q) 
        j = high + 1;
    else {
        j++;
        while (++q <= high) 
            swap(j++, q);
    }

    print(low, high - low + 1);

    // 開始遞回處理
    quick_sort_partial(low, i, depth - 1);
    // 尾遞回
    quick_sort_partial(j, high, depth);
}

#define INT_QUCICK_SORT_DEPATH      (32)

void quick_sort(int * a, int n) {
    if (a && n > 1)
        quick_sort_partial(a, a + n - 1, INT_QUCICK_SORT_DEPATH);
}

外圍代碼

#include <stddef.h>
#include <stdbool.h>

static inline void swap(int * a, int * b) {
    int t = *a;
    *a = *b;
    *b = t;
}

static void heap_adjust(int * a, ptrdiff_t n, ptrdiff_t i) {
    int node = a[i];
    for (ptrdiff_t j = 2*i+1; j < n; j = 2*i+1) {
        if (j+1 < n && a[j] < a[j+1])
            j++;
        
        // 已經是大頂堆直接結束
        if (a[j] <= node)
            break;

        a[i] = a[j];
        i = j;
    }
    a[i] = node;
}

static void heap_sort(int * a, ptrdiff_t n) {
    // 構建大頂堆
    for (ptrdiff_t i = n/2-1; i >= 0; i--)
        heap_adjust(a, n, i);

    // 資料交換
    while (--n > 0) {
        // 堆頂元素與末尾元素進行交換
        swap(a, a + n);
        // 重新對堆進行調整
        heap_adjust(a, n, 0);
    }
}

static void insert_sort(int * low, int * high) {
    for (int * lo = low + 1; lo <= high; lo++) {
        int v = *lo, * hi = lo - 1;
        if (v < *hi) {
            do {
                hi[1] = *hi;
            } while (--hi >= low && v < *hi);
            hi[1] = v;
        }
    }
}

后記

玩具好寫, 工程實戰級別還是挺有挑戰的. 技術的修行路途漫長. 代碼倉促寫完其實很不滿意, 奈何功力不夠, 下次有感悟再來浴火重生. 非常歡迎朋友交流指教. 祝好運, bye ~

標籤：其他

上一篇：C/C++編程筆記：鏈接串列（鏈表）丨洗掉節點的操作原始碼

下一篇：TimSort原始碼詳解