050. 编写快速排序算法
快速排序（Quick Sort）是一种高效的排序算法，其基本思想是通过一个“分区”操作，将数组分为两部分，其中一部分的所有元素都小于另一部分的所有元素，然后递归地对这两部分进行排序。快速排序的平均时间复杂度为 O(nlogn)，在实际应用中非常高效。 用C语言实现快速排序的代码，包括递归实现和分区函数。
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 quickSort(int arr[], int low, int high) {
if (low < high) {
// pi 是分区后的基准位置
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]);
printf("原始数组：\n");
printArray(arr, n);
quickSort(arr, 0, n - 1); // 调用快速排序函数
printf("排序后的数组：\n");
printArray(arr, n);
return 0;
}
代码说明
交换函数 swap：
- 用于交换两个整数的值。
分区函数 partition：
-
选择数组的最后一个元素作为基准（pivot）。
-
使用两个指针
i和j，其中i指向较小元素的范围，j遍历数组。 -
将小于或等于基准的元素放到左边，大于基准的元素放到右边。
-
最后将基准放到正确的位置，并返回基准的索引。
快速排序函数 quickSort：
-
通过递归调用对数组的左右两部分进行排序。
-
使用分区函数
partition来确定基准的位置，并递归地对基准左边和右边的子数组进行排序。
打印数组函数 printArray：
- 用于打印数组的内容，方便查看排序前后的结果。
示例运行
输入：
原始数组：
10 7 8 9 1 5
输出：
排序后的数组：
1 5 7 8 9 10
快速排序的特点
效率高：
-
平均时间复杂度为 O(nlogn)，在实际应用中非常高效。
-
最坏情况下（数组已经有序或完全逆序）时间复杂度为 O(n2)，但这种情况可以通过随机化选择基准来避免。
空间复杂度：
-
递归实现的空间复杂度为 O(logn)，因为递归调用会占用系统栈空间。
-
通过尾递归优化或非递归实现可以进一步减少空间复杂度。
不稳定性：
- 快速排序是一种不稳定的排序算法，即相等元素的相对顺序可能会改变。
适用性：
- 快速排序适用于大规模数据的排序，是实际应用中最常用的排序算法之一。
快速排序是一种非常高效的排序算法，通过递归和分区操作，可以快速地对数组进行排序。
视频讲解
BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)