【算法】快速排序算法的实现：C 和 C++ 版本

1. 算法简介

快速排序（Quick Sort）是由英国计算机科学家霍尔（C.A.R. Hoare）在1960年提出的一种高效的排序算法。它采用了分治法（Divide and Conquer）策略，通常具有很好的性能。在平均情况下，快速排序的时间复杂度为 O(n log n)，但在最坏情况下可能退化为 O(n^2)，不过可以通过优化策略（如随机化或三数取中法）来避免这种情况。

1.1 算法步骤

1. 选择基准元素：从待排序的数组中选择一个元素作为基准（pivot）。
2. 划分操作：将数组重新排列，使得比基准小的元素排在左边，比基准大的元素排在右边。此时，基准元素已处于排序后的正确位置。
3. 递归操作：递归地对基准左边和右边的子数组进行快速排序。

1.2 优缺点

优点：

• 平均情况下时间复杂度为 O(n log n)，性能较好。
• 空间复杂度较低，只需 O(log n) 的栈空间（递归深度）。

缺点：

• 最坏情况下时间复杂度为 O(n^2)，但可以通过随机化选择基准来优化。
• 不稳定排序，排序过程中可能会改变相同元素的相对顺序。

---

2. 使用 C 实现快速排序

首先，我们来看看如何用 C 语言实现快速排序。C 语言作为一种底层编程语言，能够提供很好的性能和灵活性。

2.1 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]);}}// 将基准元素放置到正确的位置