C语言如何用数组实现快速排序
创作时间:
作者:
@小白创作中心
C语言如何用数组实现快速排序
引用
1
来源
1.
https://docs.pingcode.com/baike/1040698
快速排序是一种高效的排序算法，基于分治法的递归排序算法，在平均情况下具有O(n log n)的时间复杂度。它通过选择一个“基准”元素，将数组分成两部分，再递归地排序这两部分。本文将详细介绍如何在C语言中用数组实现快速排序，并结合实际代码示例进行说明。
一、快速排序的基本概念和原理
快速排序（Quicksort）是由Tony Hoare在1960年提出的。它的基本思想是通过一个基准值将数组分成两个子数组，使得左子数组的所有元素都小于基准值，而右子数组的所有元素都大于基准值，然后递归地对这两个子数组进行排序。
1.1 基本步骤
- 选择基准值：通常选择数组的第一个元素、最后一个元素或中间元素作为基准值。
- 分区操作：通过一趟排序将数组分为两部分，左边部分小于等于基准值，右边部分大于等于基准值。
- 递归排序：对分区后的两个子数组继续进行快速排序。
1.2 时间复杂度
- 平均时间复杂度：O(n log n)
- 最坏时间复杂度：O(n^2)（当每次选择的基准值是数组的最大或最小值时）
- 空间复杂度：O(log n)（递归调用使用的栈空间）
二、在C语言中实现快速排序
为了在C语言中实现快速排序，我们需要实现以下几个部分：
- 交换函数：用于交换数组中的两个元素。
- 分区函数：用于将数组分成两部分。
- 快速排序函数：用于递归地排序数组。
2.1 交换函数
交换函数用于交换数组中的两个元素，代码如下：
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
2.2 分区函数
分区函数用于将数组分成两部分，使得左边部分小于等于基准值，右边部分大于等于基准值。代码如下：
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;
}
2.3 快速排序函数
快速排序函数用于递归地排序数组，代码如下：
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);
}
}
2.4 主函数
主函数用于测试快速排序算法，代码如下：
#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; 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);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quicksort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
三、快速排序的优化
尽管快速排序在平均情况下具有O(n log n)的时间复杂度，但在最坏情况下可能退化到O(n^2)。为了避免这种情况，可以采取以下几种优化措施：
3.1 随机选择基准值
通过随机选择基准值，可以减少最坏情况发生的概率。具体做法是在分区前随机选择一个元素作为基准值，并将其与当前基准值交换。
#include <stdlib.h>
int randomPartition(int arr[], int low, int high) {
int randomPivot = low + rand() % (high - low + 1);
swap(&arr[randomPivot], &arr[high]);
return partition(arr, low, high);
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = randomPartition(arr, low, high);
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
3.2 三向切分快速排序
在处理包含大量重复元素的数组时，三向切分快速排序可以显著提高效率。其基本思想是将数组分为三部分：小于基准值的部分、等于基准值的部分和大于基准值的部分。
void quicksort3way(int arr[], int low, int high) {
if (low < high) {
int lt = low, gt = high;
int pivot = arr[low];
int i = low;
while (i <= gt) {
if (arr[i] < pivot) {
swap(&arr[lt], &arr[i]);
lt++;
i++;
} else if (arr[i] > pivot) {
swap(&arr[i], &arr[gt]);
gt--;
} else {
i++;
}
}
quicksort3way(arr, low, lt - 1);
quicksort3way(arr, gt + 1, high);
}
}
四、快速排序的应用场景和注意事项
快速排序在实际应用中具有广泛的应用场景，但在使用时也需要注意一些事项。
4.1 适用场景
- 适用于大多数情况：快速排序在平均情况下表现优秀，适用于大多数需要排序的场景。
- 适用于内存限制较小的情况：快速排序的空间复杂度较低，适用于内存限制较小的情况。
4.2 注意事项
- 避免最坏情况：通过随机选择基准值或三向切分快速排序，可以有效避免最坏情况的发生。
- 处理小数组：对于较小的数组，可以使用插入排序等其他排序算法，以减少递归开销。
- 递归深度：在递归调用快速排序时，需要注意递归深度，防止栈溢出。
五、快速排序的性能分析和比较
在实际应用中，快速排序与其他排序算法相比具有较高的性能，但在某些特定情况下，其他排序算法可能表现更好。
5.1 与归并排序比较
- 时间复杂度：快速排序在平均情况下具有O(n log n)的时间复杂度，而归并排序的时间复杂度为O(n log n)。
- 空间复杂度：快速排序的空间复杂度为O(log n)，而归并排序的空间复杂度为O(n)。
- 适用场景：快速排序适用于大多数情况，而归并排序适用于需要稳定排序或处理大规模数据的情况。
5.2 与堆排序比较
- 时间复杂度：快速排序在平均情况下具有O(n log n)的时间复杂度，而堆排序的时间复杂度为O(n log n)。
- 空间复杂度：快速排序的空间复杂度为O(log n)，而堆排序的空间复杂度为O(1)。
- 适用场景：快速排序适用于大多数情况，而堆排序适用于需要稳定排序或处理大规模数据的情况。
六、总结
快速排序是一种高效的排序算法，基于分治法的递归排序算法，具有O(n log n)的时间复杂度。通过选择基准值、分区操作和递归排序，可以实现对数组的快速排序。为了避免最坏情况的发生，可以采取随机选择基准值和三向切分快速排序等优化措施。在实际应用中，快速排序具有广泛的应用场景，但在使用时也需要注意一些事项，如避免最坏情况、处理小数组和递归深度等。通过与归并排序和堆排序的比较，可以更好地了解快速排序的性能和适用场景。
七、示例代码完整实现
以下是快速排序在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; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
int randomPartition(int arr[], int low, int high) {
int randomPivot = low + rand() % (high - low + 1);
swap(&arr[randomPivot], &arr[high]);
return partition(arr, low, high);
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = randomPartition(arr, low, high);
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
void quicksort3way(int arr[], int low, int high) {
if (low < high) {
int lt = low, gt = high;
int pivot = arr[low];
int i = low;
while (i <= gt) {
if (arr[i] < pivot) {
swap(&arr[lt], &arr[i]);
lt++;
i++;
} else if (arr[i] > pivot) {
swap(&arr[i], &arr[gt]);
gt--;
} else {
i++;
}
}
quicksort3way(arr, low, lt - 1);
quicksort3way(arr, gt + 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[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quicksort(arr, 0, n - 1);
printf("Sorted array using quicksort: \n");
printArray(arr, n);
int arr2[] = {10, 7, 8, 9, 1, 5, 10, 7, 8, 9, 1, 5};
int m = sizeof(arr2) / sizeof(arr2[0]);
quicksort3way(arr2, 0, m - 1);
printf("Sorted array using 3-way quicksort: \n");
printArray(arr2, m);
return 0;
}
通过上述代码示例，可以清晰地了解如何在C语言中用数组实现快速排序，并进行优化和性能分析。希望这篇文章对你有所帮助！
热门推荐
饭店大厨教你做红烧鸡：从选材到出锅的完整攻略
广东人教你如何做出美味的葱烧鸡
鸡翅、鸡腿、鸡胸肉的最佳吃法大揭秘！
肢体语言在合唱表演艺术中的深度训练与融合
魏大勋机智救场，专业的舞台应变能力，很圈粉
重庆市气象台发布：春节出行必看！
春节打卡解放碑：重庆旅游全攻略
重庆春节文旅大集合：玩转山城迎新年！
首个“非遗中国年”：重庆春节民俗大赏
春节打卡重庆洪崖洞：千与千寻现实版！
复方倍氯米松樟脑乳膏孕妇可以擦吗
黄芪什么时间段喝最好
土耳其旅游现金攻略：带多少现金才够用？
最受欢迎的土耳其甜点
深圳7处宝藏海滩：0元打卡，人少景美，拍照绝美
营养师分享五贴士 控制饮食健康过年
猪肝舌暗藏风险，中西医解读健康密码
秋冬舌色异常？中医教你这样吃！
冬季养生从调味品开始：姜、肉桂、红枣的养生之道
秋冬养生必备：八角、丁香和小茴香的秘密武器
土耳其现在旅游安全吗？自由行背包客的风险评估与安全攻略
如何安全地接线地面插座？这种接线如何保证稳定性？
插座位置规划：家庭装修中的细节决定便利与安全
皖南自驾游必备：车辆检查清单大揭秘！
探秘西溪南：黄山脚下的世外桃源
皖南川藏线：秋色绝美摄影点大揭秘！
Android平台游戏下载黑科技揭秘！
得了胃十二指肠溃疡不用怕，教你科学治疗和预防
胃出血警讯不可忽视，从症状辨识到原因一次弄懂
泉州千年古迹：清真寺与开元寺的文化对话