在 C 语言中实现快速排序（Quick Sort）有多种方式。我们可以通过不同的 划分策略 或 递归处理方式 实现不同版本的快速排序。下面将展示三种常见版本的快速排序实现：
快速排序基本原理
快速排序是基于分治法的排序算法。基本步骤如下：
- 选择基准：从待排序的数组中选择一个元素作为基准（pivot）。
- 划分操作：将数组分为两部分，一部分小于基准，另一部分大于基准。
- 递归排序：递归地对两个子数组进行快速排序，直到子数组的大小为 1 或 0。
三种版本的快速排序实现
我们将实现三种版本的快速排序：
- 经典版本：选择基准元素为第一个元素。
- 随机基准版本：选择基准元素为数组中的随机元素。
- 三路划分版本：针对重复元素较多的情况，使用三路划分方法（荷兰国旗问题）。
1. 经典快速排序
经典的快速排序算法选择数组的第一个元素作为基准，并通过 一次划分 将数组分为两个部分。
代码实现：
#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[low]; // 选择第一个元素为基准
int left = low + 1;
int right = high;
while (left <= right) {
// 左边找到大于或等于基准的元素
while (left <= right && arr[left] <= pivot) left++;
// 右边找到小于或等于基准的元素
while (left <= right && arr[right] > pivot) right--;
if (left < right) {
swap(&arr[left], &arr[right]);
}
}
// 将基准元素放到正确的位置
swap(&arr[low], &arr[right]);
return right;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
关键点：
- 选择基准：选择第一个元素作为基准。
- 划分过程：将数组分为两部分，一部分小于基准，另一部分大于基准。
2. 随机基准版本
在经典快速排序中，选择第一个元素作为基准可能导致最坏的时间复杂度 O(n^2)，特别是当输入数据已经接近有序时。为此，可以通过 随机选择基准元素 来提高算法的性能，避免最坏情况。
代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
// 随机选择基准
int pivotIndex = low + rand() % (high - low + 1);
swap(&arr[low], &arr[pivotIndex]); // 将基准放到第一个位置
int pivot = arr[low];
int left = low + 1;
int right = high;
while (left <= right) {
while (left <= right && arr[left] <= pivot) left++;
while (left <= right && arr[right] > pivot) right--;
if (left < right) {
swap(&arr[left], &arr[right]);
}
}
swap(&arr[low], &arr[right]);
return right;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr) / sizeof(arr[0]);
// 初始化随机种子
srand(time(NULL));
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
关键点：
- 随机基准：通过
rand()函数随机选择一个基准，避免了最坏情况的出现。
3. 三路划分版本（荷兰国旗问题）
在快速排序中，如果数组中存在大量重复元素，经典的快速排序方法可能会导致性能下降。三路划分版本的快速排序可以处理这种情况，它通过将数组划分为三个部分：小于基准、等于基准、大于基准，从而减少了重复元素的处理。
代码实现：
#include <stdio.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void threeWayPartition(int arr[], int low, int high, int *lt, int *gt) {
int pivot = arr[low];
int i = low + 1;
int j = high;
*lt = low;
*gt = high;
while (i <= *gt) {
if (arr[i] < pivot) {
swap(&arr[i], &arr[*lt]);
(*lt)++;
i++;
} else if (arr[i] > pivot) {
swap(&arr[i], &arr[*gt]);
(*gt)--;
} else {
i++;
}
}
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int lt, gt;
threeWayPartition(arr, low, high, <, >);
quickSort(arr, low, lt - 1);
quickSort(arr, gt + 1, high);
}
}
int main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70, 40, 40};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
关键点：
- 三路划分：根据与基准元素的关系，将数组划分为三部分：小于基准、等于基准、大于基准，能够有效处理重复元素。
- 优化：该方法特别适合包含大量重复元素的数组。
总结
- 经典快速排序：使用数组的第一个元素作为基准，适合大多数情况。
- 随机基准快速排序：通过随机选择基准来避免最坏情况，增加算法的平均性能。
- 三路划分快速排序：通过三路划分的方式处理重复元素，避免了性能下降，适用于有大量重复元素的数组。
这些版本的快速排序可以根据具体的场景进行选择，以提高排序效率。
发表回复