快速排序

代码

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 quick_sort(int arr[], int low, int high) {
    int stack[high - low + 1];
    int top = -1;

    stack[++top] = low;
    stack[++top] = high;

    while (top >= 0) {
        high = stack[top--];
        low = stack[top--];

        int p = partition(arr, low, high);

        if (p - 1 > low) {
            stack[++top] = low;
            stack[++top] = p - 1;
        }

        if (p + 1 < high) {
            stack[++top] = p + 1;
            stack[++top] = high;
        }
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    quick_sort(arr, 0, n - 1);

    printf("\nSorted array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

代码解释

1. 初始化：数组 arr 是待排序的数组，n 是数组的长度。
2. 交换函数：
   • swap 函数用于交换两个整数的值。
3. 分区函数：
   • partition 函数选取数组的最后一个元素作为枢纽元素（pivot）。
   • i 初始化为 low - 1，用于记录小于枢纽元素的区域。
   • 遍历数组，将小于枢纽元素的元素交换到左侧。
   • 最后，将枢纽元素放置到正确的位置，并返回其索引。
4. 快速排序函数：
   • quick_sort 使用栈来模拟递归过程，实现非递归的快速排序。
   • 初始化栈，将初始区间 [low, high] 压入栈中。
   • 进入循环，每次从栈中弹出一个区间并进行分区。
   • 将分区后左右子区间压入栈，直到栈为空。

示例运行

假设输入数组为 {12, 11, 13, 5, 6, 7}：

1. 初始状态：{12, 11, 13, 5, 6, 7}
2. 第一次分区：
   • 选择枢纽元素 7。
   • 交换小于 7 的元素到左侧：{6, 5, 7, 12, 11, 13}
   • 枢纽元素 7 放置到正确位置：{6, 5, 7, 12, 11, 13}
3. 继续对左侧 [6, 5] 和右侧 [12, 11, 13] 进行分区：
   • 左侧 [6, 5] 分区后：{5, 6, 7, 12, 11, 13}
   • 右侧 [12, 11, 13] 分区后：{5, 6, 7, 11, 12, 13}
4. 最终结果：{5, 6, 7, 11, 12, 13}

时间复杂度分析

快速排序的时间复杂度主要取决于分区过程和递归深度。

• 最优时间复杂度：$O(n \log n)$，当每次分区都能将数组均匀分成两部分时。
• 最坏时间复杂度：$O(n^2)$，当每次分区都选择到最小或最大的元素作为枢纽元素，导致分区极不均匀。
• 平均时间复杂度：$O(n \log n)$，对于大多数输入数组，快速排序的性能都很稳定。

空间复杂度分析

快速排序在原地排序，但递归调用会使用栈空间，因此空间复杂度为 $O(\log n)$。

优缺点

优点：

• 时间复杂度平均为 $O(n \log n)$，适用于大规模数据排序。
• 不需要额外的辅助空间，空间复杂度低。
• 实现简单，适用于大多数情况。

缺点：

• 最坏情况下时间复杂度为 $O(n^2)$。
• 不稳定排序算法，可能改变相同元素的相对顺序。

适用场景

快速排序适用于以下场景：

• 数据量较大的排序。
• 需要一个高效且空间复杂度低的排序算法时。
• 不需要稳定排序的场景。

总结

快速排序是一种高效的排序算法，通过选择枢纽元素将数组分成两部分，分别排序后合并。尽管其最坏情况下时间复杂度较高，但在平均情况下表现优异，是一种时间复杂度低且空间复杂度低的排序算法。