排序算法‌ 之‌ 快速排序（Quick Sort）

排序算法‌ 之‌ 快速排序（Quick Sort）

1. 基础概念

1.1 快速排序的定义

快速排序是一种基于分治思想的比较排序算法。其主要思想是：通过一次排序将待排序序列划分成两个子序列，使得左子序列的所有元素小于或等于枢轴值，右子序列的所有元素大于枢轴值。然后递归地对两个子序列排序，最终得到有序数组。

1.2 快速排序的特点

• 平均时间复杂度为O(n log n)，性能优于冒泡排序、插入排序等简单排序算法。
• 不稳定排序：由于元素交换，可能打破相同元素的相对顺序。
• 原地排序：不需要额外的存储空间，空间复杂度为O(log n)。
• 最坏时间复杂度为O(n²)，通常通过随机选择枢轴来避免退化。

1.3 使用场景

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

• 数据量较大且无序的数组。
• 对空间复杂度要求较低的场景。
• 需要较高平均性能的排序任务，如数据库排序和搜索优化。

2. 实现与操作

2.1 核心操作实现

快速排序的核心操作包括选择枢轴、划分数组（Partition）和递归排序。以下为其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; // i表示小于枢轴部分的最后一个元素下标 for (int j = low; j < high; 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); // 排序右子数组 } } // 测试函数 int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("原数组: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); quickSort(arr, 0, n - 1); printf("排序后数组: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); return 0; } </stdio.h>

2.2 代码详解

• swap：用于交换数组中两个元素。
• partition：通过枢轴将数组分为左右两部分，并返回枢轴位置。
• quickSort：主函数，递归调用对数组进行排序。

3. 时间与空间复杂度分析

3.1 时间复杂度

• 平均时间复杂度：O(n log n)。
• 最坏时间复杂度：O(n²)，发生在数组已排序或逆序的情况下。
• 最佳时间复杂度：O(n log n)，发生在每次划分均匀时。

3.2 空间复杂度

• 空间复杂度：O(log n)，由于递归调用栈的空间开销。
• 优化：通过尾递归或迭代方式减少栈深度。

4. 优缺点与局限性

4.1 优点

• 平均性能优异，适合大规模数据排序。
• 原地排序，无需额外存储空间。

4.2 缺点与局限性

• 最坏情况性能较差，需随机化或改进算法。
• 不稳定排序，可能打乱相同元素的顺序。

5. 常见应用场景

5.1 实际应用

快速排序常用于数据库索引优化和内存数据排序。

6. 代码编译与运行

6.1 编译命令

运行以下命令进行编译和执行：

gcc quick_sort.c -o quick_sort && ./quick_sort

6.2 测试用例

测试用例输出：

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