C语言下快速排序(挖坑法)详解

什么是快速排序

快速排序是将一个待排序的序列分成两部分，其中一部分的所有元素都比另一部分的所有元素小，然后再对这两部分分别进行排序，递归执行该操作直到将整个序列排好为止。快速排序使用了分治思想。由于在每一次的递归过程中，都将待排序的序列分成两部分，因此处理的数据量不断减少，使得算法的效率比较高。

快速排序的实现

挖坑法

挖坑法的基本思想是首先选择一个基准数，用两个标记i和j从序列两端分别向中间扫描，当i遇到了比基准数大的数就停下来，当j遇到了比基准数小的数就停下来，然后交换i和j所指向的元素。直到i和j重合，此时就可以将基准数放在这个位置上，以此将序列分成两个子序列，然后递归地对这两个子序列进行排序。

具体实现的过程如下：

首先选择序列的第一个元素作为基准数pivot，设定i和j的初始值分别为左端点left和右端点right，然后从j开始，向左扫描序列，找出第一个小于基准数的元素，停在j位置上，这时候将pivot的值赋给i，实现了一个“挖坑”操作。接着，从i开始，向右扫描序列，找出第一个大于基准数的元素，停在i位置上，这时候就可以将j位置上的元素填到这个坑中，实现了一个“填坑”操作。随后，i和j再次向中间移动，继续扫描序列，直到i和j重合。最后，将pivot放在i/j重合的位置上，这样就将序列分成了两部分，并以此递归执行。

下面是基于挖坑法的快速排序的代码实现：

void QuickSort(int arr[], int left, int right) {
    if (left >= right) return; // 如果序列只剩下一个元素或者没有元素，则直接返回
    int i = left, j = right, pivot = arr[left]; // 初始化指针i、j，以及基准数pivot
    while (i < j) {
        while (arr[j] >= pivot && i < j) j--;
        if (i < j) arr[i++] = arr[j]; // 挖坑
        while (arr[i] <= pivot && i < j) i++;
        if (i < j) arr[j--] = arr[i]; // 填坑
    }
    arr[i] = pivot; // 将基准数放入最后的空位
    QuickSort(arr, left, i - 1); // 递归排序左边的子序列
    QuickSort(arr, i + 1, right); // 递归排序右边的子序列
}

示例说明

示例一

给定一个数组 arr = {6, 2, 7, 3, 8, 9, 4, 5, 1}，使用快速排序对其进行从小到大排序。

首先选定 arr[0]，即6作为基准数pivot。然后i和j指向数组的两端 left = 0, right = 8。从j开始，往左寻找第一个小于pivot的数，即找到了 arr[6] = 4，同时将 arr[0] 填上这个坑，得到 arr[0, 2, 7, 3, 8, 9, 4, 5, 4]；接着，从i开始，往右寻找第一个大于pivot的数，即找到了 arr[1] = 2，同时将 arr[6] 填上这个坑，得到 arr[2, 2, 7, 3, 8, 9, 6, 5, 4]。i和j在此时重合，将pivot放在这个位置上，得到了 arr[2, 2, 4, 3, 1, 5, 6, 7, 9, 8]。此时将序列分成了两部分，左半部分都小于pivot，右半部分都大于pivot，递归进行排序即可。

经过一次分割后，左半部分为 {2, 2, 4, 3, 1}，右半部分为 {5, 6, 7, 9, 8}。以左半部分为例，选择 arr[0] 作为基准数pivot，进行相同的操作，即先从右向左找到一个小于pivot的数 arr[3] = 3，用 arr[0] 填坑，得到 arr[1, 2, 4, 3, 1]；接着再从左向右找到第一个大于pivot的数 arr[2] = 4，用 arr[3] 填坑，得到 arr[1, 2, 3, 4, 1]。此时将pivot放在最后的位置上，得到 arr[1, 2, 3, 4, 6]。随后对右半部分进行相似的操作，最终得到完整的排好序的数组 arr[1, 2, 3, 4, 5, 6, 7, 8, 9]。

示例二

给定一个数组 arr = {9, 8, 7, 6, 5, 4, 3, 2, 1}，使用快速排序对其进行从大到小排序。

首先选定 arr[0]，即9作为基准数pivot。然后i和j指向数组的两端 left = 0, right = 8，从j开始寻找小于pivot的数，由于数组本身就是从大到小排列的，因此找不到小于9的数。接着，从i开始寻找大于pivot的数，找到了 arr[1] = 8，用 arr[0] 填坑，得到 arr[9, 9, 7, 6, 5, 4, 3, 2, 1]，继续寻找直到i和j重合，最后将pivot放在此位置上，即 arr[8, 9, 7, 6, 5, 4, 3, 2, 1]。此时将序列分成了两部分，左半部分都大于pivot，右半部分都小于pivot，以此递归进行后续排序。