首页 > 编程笔记 > 算法

C语言快速排序（附带源码和解析）

快速排序是一种高效的排序算法，由计算机科学家 Tony Hoare 于 1960 年代提出。这种算法采用分治法的思想，通过将大问题分解成小问题来解决复杂的排序任务。

快速排序的平均时间复杂度为 O(n log n)，在实际应用中表现优异，是许多编程语言标准库中排序函数的首选算法。

快速排序的基本原理

快速排序的核心思想是选择一个基准元素（pivot），然后将数组划分为两部分：小于基准的元素和大于基准的元素。这个过程递归地应用于划分后的子数组，直到整个数组完全有序。

具体步骤如下：

  1. 从数组中选择一个基准元素。通常选择第一个、最后一个或中间的元素作为基准。
  2. 将小于基准的元素移到基准的左边，大于基准的元素移到基准的右边。这个过程称为分区（partition）。
  3. 递归地对基准左右两侧的子数组进行快速排序。


让我们通过一个图表来直观地理解快速排序的过程：

初始数组：    [5, 2, 9, 1, 7, 6, 3]
选择基准(5)： [5, 2, 9, 1, 7, 6, 3]
分区后：      [2, 1, 3, 5, 9, 7, 6]
递归排序：    [1, 2, 3, 5, 6, 7, 9]

C语言实现快速排序

现在，让我们用C语言来实现快速排序算法。我们将定义两个主要函数：一个用于分区操作，另一个是递归的快速排序函数。

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = (low - 1);  // 小于基准的元素的索引

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于等于基准
        if (arr[j] <= pivot) {
            i++;  // 增加小于基准的元素索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        // 递归地排序基准左右两侧的元素
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

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

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: \n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

运行结果：

原始数组:
10 7 8 9 1 5
排序后的数组:
1 5 7 8 9 10

这段代码实现了快速排序算法。partition 函数负责选择基准并将数组分为两部分，quickSort 函数递归地对子数组进行排序。main 函数展示了如何使用这个排序算法。

快速排序的性能

快速排序的平均时间复杂度为 O(n log n)，这使它成为一种非常高效的排序算法。在最坏情况下，即当输入数组已经排序或反向排序时，时间复杂度可能退化到 O(n²)。然而，通过随机选择基准元素，可以大大降低这种情况发生的概率。
 

快速排序的空间复杂度为 O(log n)，这是由于递归调用栈的深度。与其他排序算法相比，快速排序的主要优势在于它的原地排序特性（冒泡排序也是原地排序），不需要额外的存储空间。

优化快速排序

尽管基本的快速排序算法已经相当高效，但我们还可以通过一些技巧来进一步优化它：


这些优化可以显著提高快速排序在实际应用中的性能，使其成为许多场景下的首选排序算法。


你可能还想关注其它 9 种排序算法：

  1. C语言冒泡排序（附带源码和解析）
  2. C语言选择排序（附带源码和解析）
  3. C语言插入排序（附带源码和解析）
  4. C语言希尔排序（附带源码和解析）
  5. C语言归并排序（附带源码和解析）
  6. C语言堆排序（附带源码和解析）
  7. C语言计数排序（附带源码和解析）
  8. C语言桶排序（附带源码和解析）
  9. C语言基数排序（附带源码和解析）

声明：《算法系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。

相关文章

精选内容