数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用随机枢轴的快速排序
快速排序是一种分治算法。在这个算法中，我们选择一个枢轴元素，然后围绕枢轴元素对数组进行划分。这两个分区使得一部分包含所有小于枢轴元素的元素，另一部分包含所有大于枢轴元素的元素。类似地，每个部分都围绕在每个部分中选择的枢轴进一步划分，这个过程一直执行到只剩下单个元素。
选择枢轴
可以在数组中选择枢轴，方法如下：
随机枢轴。
最右或最左元素作为枢轴。
中位数作为枢轴。
在本文中，我们将使用第一种方法来选择枢轴并实现快速排序算法。
问题陈述
给定一个数组。使用随机枢轴的快速排序算法对数组进行排序。
示例1
Input: [3, 1, 7, 2, 10]
Output: [1, 2, 3, 7, 10]
说明 - 假设选择3作为随机枢轴，将其与10交换，然后将3设置为枢轴并使用3作为枢轴对数组进行划分。第一次划分后，数组为[1, 2, 3, 7, 10]，其中3位于其排序位置。然后对3左侧和右侧的两个子数组调用函数，以对其余数组进行排序。
示例2
Input: [11, 32, 7, 90, 18, 34]
Output: [7, 11, 18, 32, 34, 90]
伪代码
Swap()函数的伪代码
procedure swap (*a, *b) temp = *a *a = *b *b = temp end procedure
pickRandom()函数的伪代码
procedure pickRandom (arr[], start, end) num = Random number between start and end swap arr[num] and arr[end] end procedure
partition()函数的伪代码
procedure partition (arr[], start, end)
pickRandom (arr, start, end)
pivot = arr[end]
i = start
for k = start to end - 1
if arr[k] <= pivot
swap arr[k] and arr[i]
i = i + 1
end if
end for
swap arr[i] and arr[end]
return i
end procedure
quickSort()函数的伪代码
procedure quickSort (arr[], start, end)
if start < end
p = pickRandom (arr[], start, end)
quickSort (arr[], start, p-1)
quickSort (arr[], p+1, end)
end if
end procedure
工作原理
让我们取一个未排序的数组，并从头到尾调用staaquickSort()函数。
从pickRandom()函数开始，
假设num = start和end之间的随机数 = 2
交换arr[1]和arr[end]，我们得到以下数组：
调用partition()函数后，
Pivot = arr[end] = 23
由于枢轴位于末尾，因此算法从开头开始向末尾移动。在循环中从start到end - 1取k，i = start
现在，arr[k] < arr[pivot]，所以交换arr[k]和arr[i]，i = i + 1。
现在，arr[k] < arr[pivot]，所以交换arr[k]和arr[i]，i = i + 1。
现在，arr[k] < arr[pivot]，所以交换arr[k]和arr[i]，i = i + 1。
现在，arr[k] > arr[pivot]，所以k向前移动。
现在，arr[k] > arr[pivot]并且循环结束。
循环结束后，交换arr[i]和arr[pivot]。
并返回i = 3。
因此，下一个quickSort()将对从start到i-1的数组以及从i+1到end的数组调用。
示例：C++实现
在下面的程序中，为了使用随机枢轴对数组进行快速排序，我们首先选择数组的随机索引。然后将此随机索引上的数字与数组的末尾元素交换。然后选择末尾元素作为枢轴。然后围绕此枢轴对数组进行划分，并对划分后的数组递归调用quickSort，直到每个子数组中只剩下一个元素。
#include <bits/stdc++.h>
using namespace std;
// function to swap values of two variables
void swap(int *x, int *y){
int t = *x;
*x = *y;
*y = t;
}
// This function picks a random index between start and end and swaps the value at that index to the value at end index.
void pickRandom(int arr[], int start, int end){
int num = start + rand() % (end - start + 1);
swap(arr[num], arr[end]);
}
// This function calls the pickRandom() function and then partitions the array into two subarrays
int partition(int arr[], int start, int end){
pickRandom(arr, start, end);
// End element is chosen as pivot
int pivot = arr[end];
int i = start;
for (int k = start; k < end; k++){
if (arr[k] <= pivot){
swap(arr[k], arr[i]);
i++;
}
}
swap(arr[i], arr[end]);
// The array is divided into two sub-parts with the left part having all the elements smaller than the pivot and right part having elements bigger than the pivot.
return i;
}
void quickSort(int arr[], int start, int end){
if (start < end){
// p is the point of partition
int p = partition(arr, start, end);
// Calling quicksort on left subarray
quickSort(arr, start, p - 1);
// Calling quicksort on right subarray
quickSort(arr, p + 1, end);
}
}
int main(){
int arr[6] = {19, 4, 23, 77, 31, 8};
// Before Sorting
cout << "Array before sorting : ";
for (int i = 0; i < 6; i++){
cout << arr[i] << " ";
}
// Applying quick Sort
quickSort(arr, 0, 5);
// After Sorting
cout << "\nArray after sorting : ";
for (int i = 0; i < 6; i++){
cout << arr[i] << " ";
}
return 0;
}
输出
Array before sorting : 19 4 23 77 31 8 Array after sorting : 4 8 19 23 31 77
时间复杂度 - 最坏情况复杂度 = O(n2)
平均（预期）情况复杂度 = O(nlogn)。
空间复杂度 - 由于使用了递归堆栈空间，因此为O(nlogn)。
结论
总之，使用带有随机枢轴的快速排序对数组进行排序有助于将平均或预期时间复杂度提高到O(nlogn)，但最坏情况复杂度仍然为O(n2)。
2000+ 次浏览
