作者：lidasi | 来源：互联网 | 2024-12-08 11:33
在数据结构与算法领域，快速排序是一种非常高效的排序方法。本文将通过一个具体的C语言程序实例来展示如何实现快速排序，特别是使用随机化技术来提高算法性能。
```cpp
#include
#include
#include
// 随机数生成范围为 x 到 y
// k = rand() % (y - x + 1) + x
// 交换两个整数
void swap(int& a, int& b) {
if (a != b) {
a ^= b;
b ^= a;
a ^= b;
}
}
// 随机快速排序函数
void randomizedQuicksort(int arr[], int left, int right) {
srand((unsigned)time(0)); // 使用当前时间作为随机种子
int randomIndex = rand() % (right - left + 1) + left;
swap(arr[randomIndex], arr[right]); // 将随机选中的元素与最后一个元素交换
int pivot = arr[right];
int i = left - 1;
for (int j = left; j if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[right]);
int partitiOnIndex= i + 1;
if (left randomizedQuicksort(arr, left, partitionIndex - 1);
if (partitionIndex + 1 randomizedQuicksort(arr, partitionIndex + 1, right);
}
int main() {
int arr[] = {2, 9, 71, 20, 0, 212, 364, 78, -1, 55};
int n = sizeof(arr) / sizeof(arr[0]);
randomizedQuicksort(arr, 0, n - 1);
for (int i = 0; i printf("%d ", arr[i]);
return 0;
}
```
### 解析
- **随机化**：通过 `srand` 和 `rand` 函数，每次运行时选择不同的枢轴，有助于避免最坏情况的发生，特别是在数据已经部分有序的情况下。
- **交换操作**：使用位运算进行交换，这是一种高效的方法，避免了使用临时变量。
- **递归调用**：通过递归调用 `randomizedQuicksort` 函数，实现了对数组的分治排序。
快速排序的时间复杂度平均为 O(n log n)，但在最坏情况下（例如数组已经是有序的）可能退化为 O(n^2)。通过随机化选择枢轴，可以有效减少这种情况发生的概率。
京公网安备 11010802041100号