当前位置：首页 > ops >正文

快速排序：原理、示例与 C 语言实现详解

ops 2025/7/16 15:23:10

一、算法思想

快速排序其核心思想可概括为：

分治法（Divide and Conquer）：将原问题分解为若干个规模更小但结构相似的子问题，递归地解决这些子问题，最后合并子问题的解得到原问题的解。
基准值（Pivot）选择：在待排序序列中选择一个元素作为基准值（pivot），将序列划分为两部分。
分区（Partition）操作：
- 小于基准值的元素放在基准值左边
- 大于基准值的元素放在基准值右边
- 基准值放置在中间正确的位置
递归排序：分别对左右两个子序列递归地应用快速排序算法，直至子序列长度为 1 或 0（自然有序）。

快速排序的平均时间复杂度为 O (n log n)，属于不稳定排序。

二、手动排序示例

下面通过一个具体例子展示快速排序的过程。待排序数组为：[5, 3, 8, 4, 2]

步骤 1：选择基准值

选择第一个元素 5 作为基准值（pivot=5）。

步骤 2：分区操作

初始化两个指针：左指针指向 3，右指针指向 2。

左指针向右移动，找到第一个大于等于 5 的元素（8）
右指针向左移动，找到第一个小于等于 5 的元素（2）
交换这两个元素：[5, 3, 2, 4, 8]

此时左右指针位置：

左指针指向 2（索引 2）
右指针指向 4（索引 3）

继续移动指针：

左指针右移指向 4（索引 3）
右指针左移指向 4（索引 3）
左右指针相遇，分区结束

将基准值 5 与相遇位置的元素 4 交换：[4, 3, 2, 5, 8]

步骤 3：递归处理子数组

得到两个子数组：

左子数组：[4, 3, 2]
右子数组：[8]

处理左子数组 [4, 3, 2]：

选择基准值 4
分区后：[2, 3, 4]
递归处理子数组 [2, 3] 和 []

处理子数组 [2, 3]：

选择基准值 2
分区后：[2, 3]（自然有序）

右子数组 [8] 自然有序。

最终排序结果

[2, 3, 4, 5, 8]

三、C 语言实现代码

下面是快速排序的 C 语言实现，采用 Hoare 分区方案：

#include <stdio.h>// 交换两个元素
void swap(int* a, int* b) {int t = *a;*a = *b;*b = t;
}// Hoare分区函数
int partition(int arr[], int low, int high) {int pivot = arr[low];  // 选择第一个元素作为基准值int left = low - 1;int right = high + 1;while (1) {// 找到左边第一个大于等于基准值的元素do {left++;} while (arr[left] < pivot);// 找到右边第一个小于等于基准值的元素do {right--;} while (arr[right] > pivot);// 如果指针相遇或交叉，分区完成if (left >= right)return right;// 交换左右指针指向的元素swap(&arr[left], &arr[right]);}
}// 快速排序主函数
void quickSort(int arr[], int low, int high) {if (low < high) {// 分区操作int pivotIndex = partition(arr, low, high);// 递归排序左右子数组quickSort(arr, low, pivotIndex);quickSort(arr, pivotIndex + 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[] = {5, 3, 8, 4, 2};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: ");printArray(arr, n);quickSort(arr, 0, n - 1);printf("排序后数组: ");printArray(arr, n);return 0;
}

四、代码解释

swap 函数：用于交换两个整数的值，通过指针传递参数实现。
partition 函数：
- 选择第一个元素作为基准值
- 使用左右指针向中间移动，找到需要交换的元素
- 返回分区点位置，确保左边元素≤基准值，右边元素≥基准值
quickSort 函数：
- 递归调用自身处理左右子数组
- 递归终止条件是子数组长度≤1
main 函数：
- 初始化测试数组
- 调用快速排序函数
- 输出排序前后的数组