C语言数据结构 快速排序实例详解

什么是快速排序？

快速排序（Quicksort）是一种采用分治法（Divide and Conquer）的排序算法，通过将一个大问题逐步分解为小问题来解决的一种工具。

快速排序是一个比较快的排序算法，在平均状况下，排序n个项目要 O(n log n) 次比较，最坏情况下需要O(n^2)次比较，但这种状况并不常见。

快速排序算法的基本思想

快速排序的核心思想在于分治法，具体步骤如下：

1. 选择一个枢轴元素piv；
2. 将序列中小于等于枢轴元素的元素放在左边；大于枢轴元素的元素放在右边；
3. 递归地对左右两部分进行排序。

如下图所示，在这个示例中，选取的枢轴元素为数字3，小于等于3的数放在左边，大于3的数放在右边。

             [ 5  2  6  3  8  7  1  4 ]
                      /   \
                [ 2  1  3  4 ]  [ 5  6  8  7 ]
                   /     \         /     \
               [ 1  2 ] [ 4  3 ] [ 5  6 ] [ 8  7 ]
                   \     /
                  [ 1  2  3  4 ]

快速排序的代码实现

下面我们将通过C语言来实现快速排序。这里给出两个示例，一个基于递归，另一个基于栈。

基于递归的实现

代码如下：

#include <stdio.h>

void quickSort(int *a, int left, int right) {
    int i, j, temp, pivot;
    pivot = a[left];
    i = left;
    j = right;
    if (left >= right)
        return;
    while (i < j) {
        while (a[j] >= pivot && i < j)
            j--;
        while (a[i] <= pivot && i < j)
            i++;
        if (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    a[left] = a[i];
    a[i] = pivot;
    quickSort(a, left, i - 1);
    quickSort(a, i + 1, right);
}

void main() {
    int a[] = {26, 27, 23, 17, 25, 31, 29, 19};
    int i;
    quickSort(a, 0, 7);
    for (i = 0; i < 8; i++)
        printf("%d ", a[i]);
    printf("\n");
}

基于栈的实现

代码如下：

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

typedef struct {
    int left;
    int right;
} Range;

typedef struct {
    Range r[100];
    int size;
} Stack;

Stack stack;

void push(int left, int right) {
    stack.r[stack.size].left = left;
    stack.r[stack.size].right = right;
    stack.size++;
}

Range pop() {
    stack.size--;
    return stack.r[stack.size];
}

void quickSort(int *a, int left, int right) {
    if (left >= right)
        return;
    push(left, right);
    while (stack.size > 0) {
        Range range = pop();
        int i = range.left;
        int j = range.right;
        int pivot = a[i];
        while (i < j) {
            while (a[j] >= pivot && i < j)
                j--;
            a[i] = a[j];
            while (a[i] <= pivot && i < j)
                i++;
            a[j] = a[i];
        }
        a[i] = pivot;
        if (range.left < i - 1)
            push(range.left, i - 1);
        if (range.right > i + 1)
            push(i + 1, range.right);
    }
}

void main() {
    int a[] = {35, 33, 42, 10, 14, 19, 27, 44, 26, 31};
    int i;
    quickSort(a, 0, 9);
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);
    printf("\n");
}

快速排序算法的复杂度分析

快速排序算法的时间复杂度可以分析如下：

• 最坏情况下，每次划分只能将区间缩小1，需要n次划分，时间复杂度为O(n^2)；
• 最好情况下，每次划分所得的两个子区间长度一样，需要进行log n次划分，时间复杂度为O(n log n)；
• 平均情况下，快速排序的时间复杂度为O(n log n)。

空间复杂度方面，由于采用递归或栈来实现，每次递归或产生栈帧的空间的大小为log n，所以空间复杂度为 O(log n)。

小结

快速排序算法是经典的排序算法之一，其核心思想在于分治法，适用于排序大规模数据的场景。本文通过C语言的实现代码，详细讲解了快速排序算法的基本思想、基于递归和基于栈两种实现方式，以及时间复杂度和空间复杂度等方面的分析。