快速排序的思想、时间复杂度、实现以及优化方法
原创快速排序的思想、时间复杂度、实现以及优化方法
原创
代码小李
发布于 2024-12-30 15:31:40
发布于 2024-12-30 15:31:40
快速排序的思想
快速排序（Quicksort）是一种高效的排序算法，采用分治法（Divide and Conquer）的策略。其基本思想是：
- 选择一个基准值（Pivot）：从数组中选择一个元素作为基准值。
- 分区操作（Partition）：将数组分为两部分，一部分的所有元素都小于基准值，另一部分的所有元素都大于或等于基准值。
- 递归排序：对这两部分分别递归地进行快速排序。
时间复杂度
- 最佳情况：O(n log n)，当每次分区都能均匀分割数组时。
- 平均情况：O(n log n)，在大多数情况下，快速排序的性能接近最佳情况。
- 最坏情况：O(n^2)，当每次分区都选择最小或最大元素作为基准值时，例如数组已经有序或逆序。
实现
以下是一个简单的快速排序实现：
#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 - 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) {
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("原始数组: ");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("排序后的数组: ");
printArray(arr, n);
return 0;
}优化方法
选择更好的基准值：
- 随机选择基准值：通过随机选择基准值可以减少最坏情况的发生概率。
- 三数取中法：选择数组的第一个、中间和最后一个元素的中位数作为基准值。
- 尾递归优化：
- 在递归调用时，优先处理较小的子数组，这样可以减少递归深度，避免栈溢出。
- 小数组使用插入排序：
- 对于小数组，插入排序通常比快速排序更高效。可以在数组大小小于某个阈值时切换到插入排序。
- 非递归实现：
- 使用迭代和栈来实现快速排序，避免递归带来的栈溢出问题。
示例代码优化
以下是一个包含上述优化的快速排序实现：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 交换两个元素
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 三数取中法选择基准值
int medianOfThree(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid]) swap(&arr[low], &arr[mid]);
if (arr[low] > arr[high]) swap(&arr[low], &arr[high]);
if (arr[mid] > arr[high]) swap(&arr[mid], &arr[high]);
return mid;
}
// 分区函数
int partition(int arr[], int low, int high) {
int pivotIndex = medianOfThree(arr, low, high);
int pivot = arr[pivotIndex];
swap(&arr[pivotIndex], &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 insertionSort(int arr[], int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
while (low < high) {
if (high - low < 10) { // 小数组使用插入排序
insertionSort(arr, low, high);
break;
} else {
int pi = partition(arr, low, high);
if (pi - low < high - pi) {
quickSort(arr, low, pi - 1); // 优先处理较小的子数组
low = pi + 1;
} else {
quickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
}
// 打印数组
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, 3, 2, 6, 4};
int n = sizeof(arr) / sizeof(arr[0]);
srand(time(NULL)); // 初始化随机数生成器
printf("原始数组: ");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("排序后的数组: ");
printArray(arr, n);
return 0;
}总结
快速排序是一种高效的排序算法，通过分治法将数组分成两部分并递归排序。通过选择更好的基准值、尾递归优化、小数组使用插入排序和非递归实现等方法，可以进一步提高快速排序的性能和稳定性。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
