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 分区法实现// C implementation QuickSort// using Lomutos partition Scheme.#include cstdlib#include time.h#include iostreamusing namespace std;// This function takes last element// as pivot, places// the pivot element at its correct// position in sorted array, and// places all smaller (smaller than pivot)// to left of pivot and all greater// elements to right of pivotint partition(int arr[], int low, int high){// pivotint pivot arr[high];// Index of smaller elementint i (low - 1);for (int j low; j high - 1; j){// If current element is smaller// than or equal to pivotif (arr[j] pivot) {// increment index of// smaller elementi;swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return (i 1);}// Generates Random Pivot, swaps pivot with// end element and calls the partition functionint partition_r(int arr[], int low, int high){// Generate a random number in between// low .. highsrand(time(NULL));int random low rand() % (high - low);// Swap A[random] with A[high]swap(arr[random], arr[high]);return partition(arr, low, high);}/* The main function that implementsQuickSortarr[] -- Array to be sorted,low -- Starting index,high -- Ending index */void quickSort(int arr[], int low, int high){if (low high) {/* pi is partitioning index,arr[p] is nowat right place */int pi partition_r(arr, low, high);// Separately sort elements before// partition and after partitionquickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}}/* Function to print an array */void printArray(int arr[], int size){int i;for (i 0; i size; i)coutarr[i] ;}// Driver Codeint 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) // 由于递归调用栈使用霍尔分区法的随机枢轴算法partition(arr[], lo, hi)pivot arr[lo]i lo - 1 // Initialize left indexj hi 1 // Initialize right indexwhile(True)// Find a value in left side greater than pivotdoi i 1while arr[i] pivot// Find a value in right side smaller than pivotdoj j - 1while arr[j] pivotif i j thenreturn jelseswap arr[i] with arr[j]end whilepartition_r(arr[], lo, hi)r Random number from lo to hiSwap arr[r] and arr[lo]return partition(arr, lo, hi)quicksort(arr[], lo, hi)if lo hip partition_r(arr, lo, hi)quicksort(arr, lo, p)quicksort(arr, p1, hi)使用霍尔分区法的实现// C implementation of QuickSort// using Hoares partition scheme#include cstdlib#include iostreamusing namespace std;// This function takes last element as// pivot, places the pivot element at// its correct position in sorted// array, and places all smaller// (smaller than pivot) to left of pivot// and all greater elements to rightint partition(int arr[], int low, int high){int pivot arr[low];int i low - 1, j high 1;while (true) {// Find leftmost element greater than// or equal to pivotdo {i;} while (arr[i] pivot);// Find rightmost element smaller than// or equal to pivotdo {j--;} while (arr[j] pivot);// If two pointers metif (i j)return j;swap(arr[i], arr[j]);}}// Generates Random Pivot, swaps pivot with// end element and calls the partition function// In Hoare partition the low element is selected// as first pivotint partition_r(int arr[], int low, int high){// Generate a random number in between// low .. highsrand(time(NULL));int random low rand() % (high - low);// Swap A[random] with A[high]swap(arr[random], arr[low]);return partition(arr, low, high);}// The main function that implements QuickSort// arr[] -- Array to be sorted,// low -- Starting index,// high -- Ending indexvoid quickSort(int arr[], int low, int high){if (low high) {// pi is partitioning index,// arr[p] is now at right placeint pi partition_r(arr, low, high);// Separately sort elements before// partition and after partitionquickSort(arr, low, pi);quickSort(arr, pi 1, high);}}// Function to print an arrayvoid printArray(int arr[], int n){for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);}// Driver Codeint 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) // 由于递归调用栈使用 generateRandomPivot 函数实现这里提供了一种不使用 Hoare 和 Lomuto 分区方案的实现方法。使用随机枢轴而不进行分区实现快速排序#include iostream#include cstdlib#include ctimeusing namespace std;// Function to swap two elementsvoid swap(int* a, int* b) {int temp *a;*a *b;*b temp;}// Function to generate a random pivot indexint generateRandomPivot(int low, int high) {srand(time(NULL));return low rand() % (high - low 1);}// Function to perform QuickSortvoid quickSort(int arr[], int low, int high) {if (low high) {int pivotIndex generateRandomPivot(low, high);int pivotValue arr[pivotIndex];// Swap the pivot element with the last elementswap(arr[pivotIndex], arr[high]);int i low - 1;for (int j low; j high; j) {if (arr[j] pivotValue) {i;swap(arr[i], arr[j]);}}// Swap the pivot element back to its final positionswap(arr[i1], arr[high]);// Recursively sort the left and right subarraysquickSort(arr, low, i);quickSort(arr, i2, high);}}int main() {int arr[] {5, 2, 7, 3, 1, 6, 4, 8};int n sizeof(arr)/sizeof(arr[0]);cout Original array: ;for (int i 0; i n; i) {cout arr[i] ;}quickSort(arr, 0, n-1);cout \nSorted array: ;for (int i 0; i n; i) {cout arr[i] ;}return 0;}输出原始数组5 2 7 3 1 6 4 8 排序后数组1 2 3 4 5 6 7 8随机快速排序分析笔记使用随机枢轴我们将预期或平均时间复杂度改进为 O (N log N)。最坏情况下的复杂度仍然是 O ( N^2 )。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。