C语言之快速排序算法(递归Hoare版)介绍

什么是快速排序算法？

快速排序是一种常见的排序算法，利用分治法思想，将一个大的问题分成若干个子问题，再递归解决每一个子问题，最终将这些子问题的解组合成原问题的解。它的基本思想是先通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的数据都比另外一部分的数据小，再对这两部分数据分别进行快速排序，最终完成整个数据的排序。

快速排序算法的时间复杂度为 $O(nlogn)$，并且是一种原地排序算法，不需要额外的存储空间。

怎样实现快速排序？

快速排序算法可以实现多种方法，递归楼分区是其中最常用的方法之一。其中Hoare partition是一种最常见的分区技术。分区技术是将数组分成两个部分，第一个部分是比某个值小的元素所组成的子数组，第二个子数组是比这个值大的元素组成的子数组。

递归过程中，将数组中的最左边元素作为枢轴元素，利用分治思想，将数组以枢轴元素为基准分成两个部分，对这两个部分分别递归调用，最终完成排序。

下面是C语言递归Hoare版快速排序算法的代码样例：

int partition(int *nums, int left, int right) {
    int pivot = nums[left];
    int i = left, j = right;
    while (i <= j) {
        while (nums[i] < pivot) {
            i++;
        }
        while (nums[j] > pivot) {
            j--;
        }
        if (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
    }
    return j;
}

void quicksort(int *nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot_index = partition(nums, left, right);
    quicksort(nums, left, pivot_index);
    quicksort(nums, pivot_index+1, right);
}

示例

示例一

#include <stdio.h>

int main() {
    int nums[] = {8, 3, 10, 5, 1, 2, 9, 7, 6, 4};
    int len = sizeof(nums) / sizeof(nums[0]);

    quicksort(nums, 0, len-1);

    for (int i = 0; i < len; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

输出结果为：1 2 3 4 5 6 7 8 9 10

示例二

#include <stdio.h>

int main() {
    int nums[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int len = sizeof(nums) / sizeof(nums[0]);

    quicksort(nums, 0, len-1);

    for (int i = 0; i < len; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

输出结果为：0 0 0 0 0 0 0 0 0 0

以上两个示例都展现了递归Hoare版快速排序算法的功能，可以对数组进行排序。

最后再次总结快速排序算法的时间复杂度和优点：时间复杂度为 $O(nlogn)$，比其他算法要快；是一种原地排序算法，不需要额外存储空间。