本文共 4388 字，大约阅读时间需要 14 分钟。

手写玩具 - 快速排序

来回翻阅快速排序相关算法介绍, 真是感叹大师们的大智慧 ~ 这里通过练习的角度带大家手写个玩具. 一起乐一乐, 当课外作业.

引用

算法实现的相关策略

大街上的快速排序练习作业偏地都是, 这里也是基于类似的策略去构建.

策略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 
   
    #include 
    
     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 ~