使用随机枢轴的快速排序)
本文将探讨如何使用随机枢轴实现快速排序。在快速排序中，我们首先对数组进行原地分割，使得枢轴元素左侧的所有元素都小于枢轴元素，而右侧的所有元素都大于枢轴元素。然后，我们递归地对左右两个子数组执行相同的分割过程。
与归并排序不同，快速排序不需要合并两个已排序的数组。因此，快速排序所需的辅助空间比归并排序更少，这也是它通常优于归并排序的原因。使用随机生成的枢轴可以进一步降低快速排序的时间复杂度。
我们已经讨论了两种流行的数组划分方法——霍尔划分方案和洛穆托划分方案。
建议读者已经阅读过这篇文章，或者知道如何使用这两种划分方案中的任何一种来实现快速排序。
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
基于 Lomuto 分区的随机枢轴算法
partition(arr[], lo, hi)
pivot = arr[hi]
i = lo // 用于交换的位置
for j := lo to hi – 1 do
if arr[j] <= pivot then
swap arr[i] with arr[j]
i = i + 1
swap arr[i] with arr[hi]
return i
partition_r(arr[], lo, hi)
r = Random Number from lo to hi
Swap arr[r] and arr[hi]
return partition(arr, lo, hi)
quicksort(arr[], lo, hi)
if lo < hi
p = partition_r(arr, lo, hi)
quicksort(arr, lo , p-1)
quicksort(arr, p+1, hi)
使用 Lomuto 分区法实现：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int partition(int arr[], int low, int high)
{
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (1) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j)
return j;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int partition_r(int arr[], int low, int high)
{
srand(time(0));
int random = low + rand() % (high - low);
int temp = arr[random];
arr[random] = arr[low];
arr[low] = temp;
return partition(arr, low, high);
}
void quickSort(int arr[], int low, int high)
{
if (low < high) {
int pi = partition_r(arr, low, high);
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; 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;
}
输出
已排序数组： 1 5 7 8 9 10
时间复杂度：O(N*N)
辅助空间：O(N) // 由于递归调用栈
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
