算法踩坑-快速排序

背景

最近一年开始陆陆续续的看了一些算法的书籍，都是一些比较浅显的入门类书籍，最开始看的是《啊哈算法》，这本书是在图书馆看的，看的时候我自己都有点不好意思了，这本书号称是坐在马桶上初中生都能看得懂的书，这都这么一大把年纪了还看这玩意（没有对这本书亵慢的意思），惭愧啊哈哈，这本书算是我的算法再启蒙书籍吧，大学有接触过但是没有很系统去学过，发现大学太懒了，所以说是再启蒙书籍，如果有和我一样经历的同学，可以推荐先看下这本，这本书可以帮你消除对算法的恐惧（我是这么认为的）。
我看的第二本是《数据结构与算法分析C语言描述》，这本书内容还是很丰富的，当然难度也高了不少，但是既然是自己选择的路规则也要走完，这本书我看了大概有两个月了吧，主要是周末在图书馆看的，有很多很高深的我是选择跳过的，这本书讲到的为什么的部分比怎么做的部分还多，就是讲很多的理论知识，定理之类的，使用数学的方法分析算法的时间和空间复杂度，如果对算法的复杂度感觉很迷茫，看了这本书之后一定会豁然开朗的。
最近在看的一本书《剑指Offer》，因为看过前面两本的算法书，所以这本书看起来就基本没有什么难度了，看这本书之前建议还是先了解下基本的排序算法以及算法的时间空间复杂度，否则看起来会有些困难的。这本书的第三部分讲的是代码的质量，这部分干货多多。

快排思想

快排的基本思想就是分治，使用递归把大的排序问题分解为多个小的排序问题来达到解决问题的目的。接下来看看快步的步骤：

钮元的选择

钮元选择的的好坏对快拍效率的影响还是很大的，使用三数中值分割法的分割策略是一个比较合理的选择策略，三数中值分割法是从一组N个元素中选择第 0、N/2、N-1 个元素中中间的元素作为钮元

一组元素的排序

排序的基本思路是以钮元为标准，对一组元素进行分组，如果是递增的排序规则，那么是把小于钮元的元素放在左边，大于钮元的元素放在右边，最终把钮元放在中间某个合适的位置，这个位置也就是这个钮元最终的位置。

上面是一组元素排序的整体思路，具体的细节接下来探讨下：
比如有一组元素：16、15、13、3、8、7
选取了钮元之后：7、15、13、3、8、16 （16、13、7这三个元素中选取钮元，中间的为钮元，即13）
隐藏钮元之后： 7、15、8、3、13、16 （把钮元放在N-2的位置，13）
遍历指针：P1指向最左边的元素（7）、P2指向钮元最右边的元素（3）
指针移动：P1向右移动，直到找到一个大于钮元的元素为止，P2向左移动，直到找到一个小于钮元的元素为止
第一次：P1指向了（15），P2指向了（3）
交互P1、P2的元素： 7、3、8、15、13、16
移动指针：
第二次：P1指向了（15），P2指向（8），两个指针相遇了，把钮元归位到P1指针的位置
最终结果： 7、3、8、13、15、16
以钮元（13）为界，左边的都比13小，右边的都比13大，接下来执行下面的分治和递归步骤

分治和递归

以钮元为届，假设钮元的位置为M，对左半边（0，M-1）和右半边（M+1, N-1）重复钮元的选择和一组元素的排序的步骤，直到一组元素到不可分割的单元为止。
以 7、3、8、13、15、16 第一次排序的结果来分析，右边7、3、8这三个元素和左边的15、16 这两个元素的处理方式重复钮元的选择和一组元素的排序的步骤，最终得到的结果：3、7、8、13、15、16

快排实现

核心算法

根据以上的分析，使用代码的实现如下：

void swap(ElementType* a, ElementType* b) {
    ElementType tmp = *a;
    *a = *b;
    *b = tmp;
}

// 获取钮元
ElementType Median3(ElementType arr[], int left, int right) {
    ElementType center = (left + right) / 2;
    if (arr[left] > arr[center]) {
        swap(&arr[left], &arr[center]);
    }
    if (arr[left] > arr[right]) {
        swap(&arr[left], &arr[right]);
    }// Left<-min
    if (arr[center] > arr[right]) {
        swap(&arr[center], &arr[right]);
    }// Right<-max
    // Left < Center < Rightr
    // 最大的值是固定在最右边的
    // 钮元放在 right-1 位置
    swap(&arr[center], &arr[right - 1]);
    return arr[right - 1];
}

#define CutOff  (3)

void QSortCore(ElementType arr[], int left, int right) {
    if (left >= right) {
        // 一个元素的情况
        return;
    }
    if (right - left < CutOff) {
        // 使用插入排序
        Insertionsort(arr + left, right - left + 1);
    } else {
        ElementType pivot = Median3(arr, left, right);
        
        int rightPointer = right - 1; // 因为arr[--rightPointer]所以从right-2位置开始
        int leftPointer = left;
        
        while (leftPointer < rightPointer) {
            
            while (arr[--rightPointer] > pivot) { }
            
            while (arr[++leftPointer] < pivot) { }
            
            if (leftPointer < rightPointer) {
                swap(&arr[rightPointer], &arr[leftPointer]);
            }
        }
        // 复位钮元，需要使用leftPointer,
        // leftPointer指向的值确保都是大于等于钮元的值
        // rightPointer会出现小于钮元的值，复位钮元会出问题
        swap(&arr[leftPointer], &arr[right - 1]);
        
        // 左边递归
        QSortCore(arr, left, leftPointer - 1);
        
        // 右边递归
        QSortCore(arr, leftPointer + 1, right);
    }
}

void Quicksort(ElementType arr[], int count) {
    QSortCore(arr, 0, count-1);
}

测试案例

void testQuickSort() {
    unsigned int seed = (unsigned int)time(NULL);
    srand(seed);
    
    int count = 20;
    ElementType arr[count];
    for (int i = 0; i < count; i++) {
        arr[i] = rand() % count;
    }
    
    printf("原始数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");
    
    // 快速排序
    _Bool useQuickSort = 1;
    if (useQuickSort) {
        Quicksort(arr, count);
        printf("排序数据：\n");
        printArr(arr, count, ascRule);
        printf("\n");
    }
}

int printArr(ElementType arr[], int count, _Bool (*ruleFunPtr)(ElementType a, ElementType b)) {
    _Bool isValid = 1;
    ElementType lstItem = INT16_MAX;
    for (int i = 0; i < count; i++) {
        printf("%d ", arr[i]);
        if (lstItem != INT16_MAX) {
            if (!ruleFunPtr(lstItem, arr[i])) {
                isValid = 0;
            }
        }
        
        lstItem = arr[i];
    }
    if (isValid) {
        printf("\nValid\n");
    } else {
        printf("\nInValid\n");
    }
    return 1;
}

_Bool ascRule(ElementType a, ElementType b) {
    return a <= b;
}

_Bool descRule(ElementType a, ElementType b) {
    return a >= b;
}

测试输出：

原始数据：
16 9 17 15 15 0 19 13 1 13 3 5 13 19 7 17 2 2 7 13 
InValid

排序数据：
0 1 2 2 3 5 7 7 9 13 13 13 13 15 15 16 17 17 19 19 
Valid

快排优化

快排在元素序列比较长的情况是有优势的，但是在元素序列比较短的时候，从选取钮元，然后到递归调用的步骤，比起像插入排序这些算法反而没有了优势，所以合理的优化步骤是当元素序列小于某个值的时候使用插入排序来优化这部分的时间

 if (right - left < CutOff) {
        // 使用插入排序
        Insertionsort(arr + left, right - left + 1);
    }

时间分析

最坏时间

最坏的时间当钮元选取在最大或者最小的极端情况下发生：
T(N) = T(N-1) + N
T(N-1) = T(N-2) + N - 1
T(N-2) = T(N-3) + N - 2
...
T(2) = T(1) + 2
=>
T(N) = T(1) + ∑i(i = 2-N) = O(N²)

最好时间

最好的时间当钮元选择在中间的位置时候：
T(N) = 2T(N/2) + N
T(N/2) =2 T(N/4) + N
T(N/4) = 2T(N/8) + N
=>
T(N)/N = T(N/2)/N/2 + 1
T(N/2)/(N/2) = T(N/4)/(N/4) +1
T(N/4)(N/8) = T(N/8)/(N/16) +1
...
T(N)/N = T(1)/1 + logN
T(N) = NlogN

平均情况

平均情况的分析比较复杂，时间复杂度也是NlogN

代码位置

噢！我是算法，点我