C语言之快速排序

一简介

二代码实现

快速排序基本原理：

C语言实现快速排序的核心函数：

三时空复杂度

A.时间复杂度

B.空间复杂度

C.总结：

一简介

快速排序是一种高效的、基于分治策略的比较排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。

二代码实现

以下是使用C语言实现快速排序的基本步骤和代码示例：

快速排序基本原理：

选择一个基准元素（pivot），通常选择数组的第一个元素或者最后一个元素。
将所有比基准小的元素移动到基准元素之前，所有比基准大的元素移动到基准之后。这个操作被称为分区操作（partition）。
对基准左右两边的子数组分别递归地进行上述操作。

C语言实现快速排序的核心函数：

#include <stdio.h>

// 分区操作，返回基准元素最后的位置
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 基准元素（这里选取了数组的最后一个元素）
    int i = (low - 1);  // 指针i初始化为low - 1

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准元素，则与指针i所指向位置的元素交换，并将i后移一位
        if (arr[j] <= pivot) {
            i++;
            // 交换arr[i]和arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 把基准元素放到正确的位置（即所有小于它的元素都在它前面）
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return (i + 1);
}

// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi是基准元素最后所在的位置
        int pi = partition(arr, low, high);

        // 对基准元素左侧子数组进行递归排序
        quickSort(arr, low, pi - 1);

        // 对基准元素右侧子数组进行递归排序
        quickSort(arr, pi + 1, high);
    }
}

// 测试快速排序
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    
    printf("Sorted array: \n");
    for (int i=0; i<n; i++)
        printf("%d ", arr[i]);
    return 0;
}

这段代码首先定义了一个partition函数，该函数负责对输入数组进行一次划分操作，然后通过quickSort函数递归地对左右两个子数组执行同样的操作，直到子数组只剩下一个元素为止（因为只有一个元素的数组被认为是有序的）。最终，整个数组会被排序完成。

三时空复杂度

A.时间复杂度

平均情况：当每次划分都能将数组大致均分为两个子数组时，快速排序的平均时间复杂度为 $O(nlog_2n)$ 。这是由于每次递归调用都会将问题规模减半，并且需要对 n 个元素进行 $log_2n$ 层递归。
最好情况：最好的情况即每次选取的基准都能将数组完美地划分为大小相等的两部分，此时时间复杂度也是 $O(nlog_2n)$ 。
最坏情况：最坏的情况是每次划分后，一个子数组为空或只有一个元素，而另一个子数组包含所有剩余元素。例如，对于已经完全有序的数组，这种情况会导致退化为 $O(n^2)$ 的时间复杂度。然而，在实际应用中，可以通过随机化选择基准元素（如三数取中法）来避免这种极端情况的发生，从而保证快速排序在期望下的时间复杂度仍为 $O(nlog_2n)$ 。

B.空间复杂度

递归栈空间：快速排序是一种递归算法，其递归深度取决于输入数据的结构。在最坏情况下，递归深度可以达到 n，所以空间复杂度为 O(n)。但大多数情况下，递归深度为 $log_2n$ ，此时的空间复杂度主要来自于递归调用栈，约为 $O(log_2n)$ 。
辅助空间：快速排序在原地排序的情况下不需要额外的数据存储空间，除了递归调用栈所占用的空间外，算法本身不使用其他额外空间，因此辅助空间复杂度可认为是 O(1)。