C语言 (QuickSort using Random Pivoting)使用随机枢轴的快速排序

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