快速排序

快速排序（Quick Sort）

快速排序是很重要的算法，与傅里叶变换等算法并称二十世纪十大算法。

快速排序之所以快，是因为它使用了分治法。快速排序在每一轮挑选一个基准（pivot）元素，并让其它比它小的元素移动到数列一边，比它大的元素移动到数列的另一边，从而把数列拆解成了两个部分。

选择基准元素最简单的方式是选择数列的第一个元素。这种选择在绝大多数情况下是没有问题的，但是如果对一个原本逆序的数列进行升序排序，整个数列并没有被分成一半，每一轮仅仅确定了基准元素的位置。这种情况下数列第一个元素要么是最小值，要么是最大值，根本无法发挥分治法的优势。在这种极端情况下，快速排序需要进行n轮，时间复杂度退化成了 $O(n^2)$ 。

如何避免这种极端情况呢？可以不选择数列的第一个元素，而是随机选择一个元素作为基准元素。这样一来，即使是在数列完全逆序的情况下，也可以有效地将数列分成两部分。当然，即使是随机选择，每一次也有一定的几率选到数列的最大值或最小值（当元素互异、子数组有m>1个元素时，概率为2/m），同样会对分治造成一定影响。

确定了基准值后，如何实现将小于基准的元素都移动到基准值一边，大于基准值的都移动到另一边呢？

例如一个有8个数字组成的无序序列，进行升序排序。选定基准元素pivot，设置两个指针left和right，指向数列的最左和最右两个元素。

从right指针开始，把指针所指向的元素和基准元素做比较。如果大于或等于pivot，则right指针向左移动；如果比pivot小，则把right所指向的元素填入left指针所指向的位置，同时left向右移动一位。

接着，切换到left指针进行比较，把指针所指向的元素和基准元素做比较。如果小于或等于pivot，则left指针向右移动；如果大于pivot，则把left所指向的元素填入right指针所指向的位置，同时right向左移动一位。

重复之前的步骤继续排序：

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

当left和right指针重合在同一位置的时候，把之前的pivot元素的值填入该重合的位置。此时数列左边的元素都小于或等于基准元素，数列右边的元素都大于或等于基准元素。

算法分析

分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又被拆分成两部分，直到不可再分为止。这样平均情况下需要 $logn$ 轮，因此快速排序算法的平均时间复杂度是 $O(nlogn)$ 。

时间复杂度	空间复杂度	稳定性	设计思想
平均 $O(n\log n)$ ，最坏 $O(n^2)$	平均 $O(\log n)$ ，最坏 $O(n)$	不稳定	分治法

快速排序

原稿图示采用填坑法；下方示例代码采用双指针交换法。两者都完成分区，但元素移动的步骤不同。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        T pivot = arr[start];

        int pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

随机选择基准值

快速排序利用分治法，通过一趟排序将数组分为两部分，其中一部分小于等于基准值，另一部分大于等于基准值，然后再递归对两个子问题排序。

基本的快速排序采用序列的第一个元素作为基准值，但是这不是一种好方法。当数组已经有序时，这样的分割效率非常糟糕。为了缓解这种极端情况，可以在待排序数组中随机选择一个元素作为基准值。

随机选取基准值

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        int pivot_index = rand() % (end - start + 1) + start;
        swap(arr[start], arr[pivot_index]);
        T pivot = arr[start];

        pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

三数取中

虽然随机选取基准值可以减少出现分割不好的几率，但是最坏情况下还是 $O(n^2)$ 。另一种选取基准值的方法就是三数取中，也就是取序列中start、mid、end三个元素的中间值作为基准值。

三数取中

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        int pivot_index = median_of_three(arr, start, end);
        swap(arr[start], arr[pivot_index]);
        T pivot = arr[start];

        pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

三数取中+插入排序

对于很小和部分有序的数组，快速排序的效率不如插入排序。因此当待排序数组被分割到一定大小后，可直接采用插入排序。

三数取中+插入排序

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start >= end) {
        return;
    }
    if (end - start <= INSERTION_SORT_THRESHOLD) {
        T temp[end - start + 1];
        memcpy(temp, arr + start, sizeof(T) * (end - start + 1));
        insertion_sort(temp, end - start + 1);
        memcpy(arr + start, temp, sizeof(T) * (end - start + 1));
        return;
    }

    int pivot_index = median_of_three(arr, start, end);
    swap(arr[start], arr[pivot_index]);
    T pivot = arr[start];

    pivot_index = partition(arr, start, end, pivot);
    __quick_sort(arr, start, pivot_index - 1);
    __quick_sort(arr, pivot_index + 1, end);
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

示例沿用原始程序。C基础分区函数原先整段被注释，已恢复；小区间优化增加空区间判断。C++中的变长数组改为标准vector，其余排序过程保持原实现。

题目

一次分区完成后，哪些位置已经确定为最终位置？

题目

为什么填坑法扫描时也要处理等于pivot的值？

对[5,8,2,7,1,6]执行一次原稿填坑分区，首元素5作为pivot。写出每次指针移动、填坑后的数组（用∅标明空位）、pivot写回位置，以及下一步要处理的两个区间。无需继续排序子区间。

快速排序

快速排序（Quick Sort）

快速排序是很重要的算法，与傅里叶变换等算法并称二十世纪十大算法。

确定了基准值后，如何实现将小于基准的元素都移动到基准值一边，大于基准值的都移动到另一边呢？

例如一个有8个数字组成的无序序列，进行升序排序。选定基准元素pivot，设置两个指针left和right，指向数列的最左和最右两个元素。

重复之前的步骤继续排序：

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

算法分析

时间复杂度	空间复杂度	稳定性	设计思想
平均 $O(n\log n)$ ，最坏 $O(n^2)$	平均 $O(\log n)$ ，最坏 $O(n)$	不稳定	分治法

快速排序

原稿图示采用填坑法；下方示例代码采用双指针交换法。两者都完成分区，但元素移动的步骤不同。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        T pivot = arr[start];

        int pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

随机选择基准值

快速排序利用分治法，通过一趟排序将数组分为两部分，其中一部分小于等于基准值，另一部分大于等于基准值，然后再递归对两个子问题排序。

随机选取基准值

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        int pivot_index = rand() % (end - start + 1) + start;
        swap(arr[start], arr[pivot_index]);
        T pivot = arr[start];

        pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

三数取中

三数取中

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start < end) {
        int pivot_index = median_of_three(arr, start, end);
        swap(arr[start], arr[pivot_index]);
        T pivot = arr[start];

        pivot_index = partition(arr, start, end, pivot);
        __quick_sort(arr, start, pivot_index - 1);
        __quick_sort(arr, pivot_index + 1, end);
    }
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

三数取中+插入排序

对于很小和部分有序的数组，快速排序的效率不如插入排序。因此当待排序数组被分割到一定大小后，可直接采用插入排序。

三数取中+插入排序

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

const int INSERTION_SORT_THRESHOLD = 10;

/**
 * Binary Insertion Sort
 */
static T *insertion_sort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (temp < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }

    return arr;
}

static int partition(T *arr, int start, int end, T pivot) {
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] >= pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[start], arr[j]);
    return j;
}

static int median_of_three(T *arr, int start, int end) {
    int mid = start + (end - start) / 2;

    if (arr[start] > arr[mid]) {
        swap(arr[start], arr[mid]);
    }
    if (arr[start] > arr[end]) {
        swap(arr[start], arr[end]);
    }
    if (arr[mid] > arr[end]) {
        swap(arr[mid], arr[end]);
    }

    return mid;
}

/**
 * Quick Sort
 */
static void __quick_sort(T *arr, int start, int end) {
    if (start >= end) {
        return;
    }
    if (end - start <= INSERTION_SORT_THRESHOLD) {
        T temp[end - start + 1];
        memcpy(temp, arr + start, sizeof(T) * (end - start + 1));
        insertion_sort(temp, end - start + 1);
        memcpy(arr + start, temp, sizeof(T) * (end - start + 1));
        return;
    }

    int pivot_index = median_of_three(arr, start, end);
    swap(arr[start], arr[pivot_index]);
    T pivot = arr[start];

    pivot_index = partition(arr, start, end, pivot);
    __quick_sort(arr, start, pivot_index - 1);
    __quick_sort(arr, pivot_index + 1, end);
}

T *quick_sort(T *arr, int n) {
    srand(time(NULL));
    __quick_sort(arr, 0, n - 1);
    return arr;
}

int main() {
    int arr[] = {4, 7, 6, 5, 3, 2, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

示例沿用原始程序。C基础分区函数原先整段被注释，已恢复；小区间优化增加空区间判断。C++中的变长数组改为标准vector，其余排序过程保持原实现。

题目

一次分区完成后，哪些位置已经确定为最终位置？

题目

为什么填坑法扫描时也要处理等于pivot的值？

快速排序

快速排序

快速排序（Quick Sort）

快速排序：填坑法的完整过程

算法分析

普通快速排序：双指针比较与交换

随机选择基准值

随机基准快速排序：选择基准，再分区

三数取中

三数取中快速排序：比较三个候选

三数取中+插入排序

三数取中与插入排序：切换处理小区间

知识测验

知识测验

追踪一次填坑分区

快速排序

快速排序

快速排序（Quick Sort）

快速排序：填坑法的完整过程

算法分析

普通快速排序：双指针比较与交换

随机选择基准值

随机基准快速排序：选择基准，再分区

三数取中

三数取中快速排序：比较三个候选

三数取中+插入排序

三数取中与插入排序：切换处理小区间

知识测验

知识测验

追踪一次填坑分区