快速排序算法详解：多种实现方式与优化技巧
创作时间:
作者:
@小白创作中心
快速排序算法详解：多种实现方式与优化技巧
引用
CSDN
1.
https://blog.csdn.net/Yyyyyyyyyyyyds/article/details/145539179
快速排序是一种在实践中广泛使用的高效排序算法。它基于分治策略，平均时间复杂度为O(n log n)，使其成为处理大型数据集的理想选择。本文将深入探讨快速排序的各种实现方式、优化技巧以及非递归实现，并通过C语言代码示例进行详细讲解。
一、经典快速排序
- 基本思想
快速排序的核心在于分而治之。想象一下，你要整理一堆书，你可以随机选一本书作为“基准”，然后把其他的书分成两堆：一堆是书名排在基准之前的，另一堆是排在基准之后的。接着，你再分别对这两堆书重复这个过程。这就是快速排序的基本思想！
- 步骤
- 选择基准(Pivot Selection)：从数组中选取一个元素作为基准（pivot）。基准的选择会影响排序效率，后面会介绍优化方法。
- 分区操作(Partitioning)：重新排列数组，使得所有小于基准的元素位于基准之前，所有大于基准的元素位于基准之后。基准元素在此过程中会被放置在其最终排序位置。
- 递归排序(Recursive Sorting)：递归地对基准元素左右的两个子数组进行快速排序。
- C语言代码示例
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 partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = low - 1;
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 swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
- 代码解释
quickSort(arr[], low, high)：递归函数，对数组arr中从索引low到high的元素进行排序。递归结束的条件是low >= high，意味着子数组已经为空或者只包含一个元素，不需要再排序。partition(arr[], low, high)：关键函数！它选择最后一个元素作为基准，并执行分区操作，将数组划分为两个部分。i用于追踪小于基准的元素的索引。swap函数用于交换两个元素的位置。swap(int* a, int* b)：一个简单的交换函数，用于交换两个整数的值。
二、快速排序 - 挖坑法
- 基本思想
挖坑法是一种巧妙的分区策略。可以这样想象：你先选一个基准数，把它“挖”出来，形成一个“坑”。然后，从数组两端开始，找到合适的数来填补这个“坑”，同时产生新的“坑”，直到左右指针相遇。
- 步骤
- 选择基准(Pivot Selection)：选择数组中的某个元素作为基准（通常选择第一个元素）。
- 挖坑填数(Digging and Filling)：
- 将基准元素挖出，形成第一个“坑”。
- 从数组右端开始，寻找小于基准的元素，找到后填入左边的“坑”，并形成新的“坑”。
- 从数组左端开始，寻找大于基准的元素，找到后填入右边的“坑”，并形成新的“坑”。
- 重复上述过程，直到左右指针相遇
- 放置基准(Pivot Placement)：将基准元素放入左右指针相遇的位置，完成分区。
- C语言代码示例
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] <= pivot) i++;
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}
}
- 代码解释
关键在于while (i < j)循环中的填坑操作。理解指针i和j的移动和值的覆盖是理解这个算法的关键。
三、快速排序 - 前后指针法
- 基本思想
前后指针法使用两个指针，i和j。指针i指向小于基准的子数组的末尾，而指针j用于遍历整个数组。如果j遇到的元素小于基准，则将其交换到i的后面，并增加i。
- 步骤
- 选择基准(Pivot Selection)：选择数组中的某个元素作为基准（通常选择最后一个元素）。
- 移动指针(Moving Pointers)：
- 使用指针
j遍历数组。 - 如果
arr[j]小于基准，则将arr[j]与arr[i+1]交换，并递增i。 - 放置基准(Pivot Placement)：将基准元素放到正确的位置。
- C语言代码示例
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[high]);
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}
}
- 代码解释
i始终指向小于pivot的区域的下一个位置。在循环过程中，i之前的元素都小于pivot。
四、性能优化
- 三数取中
- 问题：如果基准元素选择不当（例如，总是选择最大或最小元素），快速排序可能会退化到O(n²)的时间复杂度。
- 解决方案：三数取中法。从数组的第一个、中间和最后一个元素中选择中间值作为基准。这可以有效避免最坏情况的发生。
- 步骤：
- 计算中间位置：
mid = (low + high) / 2。 - 比较
arr[low]、arr[mid]和arr[high]，并将中间值与arr[high]交换。
- C代码示例
void quickSort(int arr[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
if (arr[mid] < arr[low]) swap(&arr[mid], &arr[low]);
if (arr[high] < arr[low]) swap(&arr[high], &arr[low]);
if (arr[mid] < arr[high]) swap(&arr[mid], &arr[high]);
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[high]);
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}
}
- 针对重复值优化
- 问题：当数组中存在大量重复元素时，快速排序的性能会下降。
- 解决方案：在分区过程中，将所有等于基准的元素集中到一起，避免对它们进行递归排序。这通常被称为“三向切分”。
- C代码示例
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = arr[low];
int lt = low;
int gt = high;
int i = low + 1;
while (i <= gt) {
if (arr[i] < pivot) {
swap(&arr[i], &arr[lt + 1]);
lt++;
i++;
} else if (arr[i] > pivot) {
swap(&arr[i], &arr[gt]);
gt--;
} else {
i++;
}
}
quickSort(arr, low, lt - 1);
quickSort(arr, gt + 1, high);
}
}
- 代码解释
此版本将数组划分为三个部分：小于基准值、等于基准值和大于基准值。等于基准值的部分在递归调用中被排除，从而提高了具有许多重复项的数组的性能。
五、快速排序 - 非递归实现
- 基本思想
递归版本的快速排序在处理大型数组时可能会导致栈溢出。非递归实现通过使用栈来模拟递归调用，从而避免栈溢出的问题。
- 步骤
- 初始化栈(Initialize Stack)：将初始的分区范围（low和high）压入栈。
- 循环处理(Loop Processing)：从栈中弹出一个分区范围，进行分区操作。
- 压入子分区(Push Sub-partitions)：将左右子分区的范围压入栈中，以便后续处理
- C语言代码示例
#include <stdio.h>
#include <stdlib.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 quickSortNonRecursive(int arr[], int low, int high) {
int *stack = (int *)malloc(sizeof(int) * (high - low + 1) * 2);
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;
}
}
free(stack);
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSortNonRecursive(arr, 0, n - 1);
printf("Sorted array: \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
- 代码解释
- 使用动态分配的栈来避免固定大小的栈的限制。
- 在算法结束时释放动态分配的内存以避免内存泄漏。
- 栈存储要处理的分区的边界。
- 该算法迭代地从栈中弹出分区边界，对分区进行分区，并将新分区推入栈中，直到所有分区都被处理完毕。
合适的基准和采用适当的优化策略，可以充分发挥其性能优势。理解快速排序的不同实现方式有助于在实际应用中选择最合适的算法变体。无论是经典递归实现还是非递归实现，快速排序都是每个程序员工具箱中不可或缺的一部分。
热门推荐
春节习俗揭秘：你绝对想不到的年味老讲究！
思维导图怎么制作？五个轻松制作步骤拆解＋高效必备软件分享
从中专女生到保研清华，并不只是“人生逆袭”
利用AI提升论文写作效率：高效提示词指南
原神砂糖值得培养吗？砂糖圣遗物-武器-队伍搭配攻略
写给小白的AI入门科普
刁钻“老白”也认可《十日终焉》！番茄巅峰榜“引领网文新圈层”
逆变器：现代能源利用中不可或缺的电力转换设备与其重要性解析
猕猴桃的健康益处与食用指南，每天几颗最适合？
如何在流感季做好家庭防护？
为什么谣言总能迅速传播？——揭秘传谣背后的认知机制
孙子：兵法的智慧与历史的影响
21.04亿元票房！2024年国庆档电影市场洞察报告发布
如何高效地进行测试报告编写？【详尽指南】
淮山：营养宝库，健康守护的神奇食材
字旁字大全：揭秘汉字结构与文化内涵
十大让你毛骨悚然的动漫战斗
争吵时刻：如何避免冷战，有效化解矛盾
《三国志》中的女性角色与女性地位在三国时期的体现
汽车发电机结构与工作原理解析
为什么你的感情总是失败？揭秘‘舔狗’情感困境背后的心理学
软件设计模式：提升代码质量的最佳实践
初到惠州，如何租房？租房攻略指南
泰拉瑞亚官方网址 泰拉瑞亚吧 地图生成机制
凌晨4点，巴萨迎战西甲倒2：输球将落后皇马10分，前3难保
机械化学 "Cage on MOF”策略实现乙烯乙炔气体吸附和分离
陕飞：严把质量促提升
牙齿矫正手术的最佳年龄是几岁？如何挑选合适的矫正器，了解口碑和怎么样
如何做有说服力的PPT ——从胡乱堆积到有理有据
做好 PPT 后如何对员工进行培训