随机快速排序算法
快速排序是一种流行的排序算法，它选择一个枢轴元素，并围绕该枢轴元素对输入列表进行排序。要了解更多关于快速排序的信息，请点击此处
。随机快速排序旨在降低算法在最坏情况下时间复杂度为O(n2)的概率。当输入是一个已排序的列表时，快速排序的最坏时间复杂度会出现，这会导致 n(n – 1) 次比较。有两种方法可以随机化快速排序 −
随机打乱输入：对输入列表进行随机化，使已排序的输入再次打乱，从而降低时间复杂度。然而，随机快速排序通常不会执行此操作。
随机选择枢轴元素：将枢轴元素设为随机变量是随机快速排序中常用的方法。在这种情况下，即使输入已排序，枢轴也是随机选择的，从而避免了最坏情况的时间复杂度。
随机快速排序算法
该算法完全遵循标准算法，只是它随机化了枢轴的选择。
伪代码
partition-left(arr[], low, high)
pivot = arr[high]
i = low // 交换位置
for j := low to high – 1 do
if arr[j] <= pivot then
swap arr[i] with arr[j]
i = i + 1
swap arr[i] with arr[high]
return i
partition-right(arr[], low, high)
r = Random Number from low to high
Swap arr[r] and arr[high]
return partition-left(arr, low, high)
quicksort(arr[], low, high)
if low < high
p = partition-right(arr, low, high)
quicksort(arr, low , p-1)
quicksort(arr, p+1, high)
示例
让我们通过一个例子来了解随机快速排序如何避免最坏情况的时间复杂度。由于我们正在设计随机算法来降低时间复杂度中最坏情况的发生率，因此本例中我们以一个排序列表作为输入。
排序后的输入列表为 3、5、7、8、12、15。我们需要应用快速排序算法对列表进行排序。
步骤 1
考虑可能的最坏情况，如果所选的随机主元也是最高索引号，则它会比较所有其他数字，并选择另一个主元。
由于 15 大于列表中的所有其他数字，因此不会交换它，而是选择另一个主元。已选定。
步骤 2
这次，如果随机枢轴函数选择 7 作为枢轴数 −
现在枢轴将列表分成两半，因此通常会执行标准快速排序。然而，时间复杂度比最坏情况有所降低。
需要注意的是，快速排序的最坏时间复杂度始终保持为 O(n2)，但通过随机化，我们可以减少最坏情况的发生。
实现
以下是上述方法在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 交换两个元素的函数
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 数组分区函数
int partition_left(int arr[], int low, int high) {
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[high]);
return i;
}
// 执行随机分区的函数
int partition_right(int arr[], int low, int high) {
srand(time(NULL));
int r = low + rand() % (high - low);
swap(&arr[r], &arr[high]);
return partition_left(arr, low, high);
}
// 快速排序的递归函数
void quicksort(int arr[], int low, int high) {
if (low < high) {
int p = partition_right(arr, low, high);
quicksort(arr, low, p - 1);
quicksort(arr, p + 1, high);
}
}
// 打印数组的函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("
");
}
// 驱动代码
int main() {
int arr[] = { 6, 4, 12, 8, 15, 16};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组： ");
printArray(arr, n);
quicksort(arr, 0, n - 1);
printf("排序数组： ");
printArray(arr, n);
return 0;
}
输出
原始数组： 6 4 12 8 15 16 排序数组： 4 6 8 12 15 16
#include <iostream>
#include <cstdlib>
#include <ctime>
// 交换两个元素的函数
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 数组分区函数
int partitionLeft(int arr[], int low, int high) {
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, high);
return i;
}
// 执行随机分区的函数
int partitionRight(int arr[], int low, int high) {
srand(time(NULL));
int r = low + rand() % (high - low);
swap(arr, r, high);
return partitionLeft(arr, low, high);
}
// 快速排序的递归函数
void quicksort(int arr[], int low, int high) {
if (low < high) {
int p = partitionRight(arr, low, high);
quicksort(arr, low, p - 1);
quicksort(arr, p + 1, high);
}
}
// 打印数组的函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
// 驱动代码
int main() {
int arr[] = {6, 4, 12, 8, 15, 16};
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << "原始数组： ";
printArray(arr, n);
quicksort(arr, 0, n - 1);
std::cout << "排序数组： ";
printArray(arr, n);
return 0;
}
输出
原始数组： 6 4 12 8 15 16 排序数组： 4 6 8 12 15 16
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
// 交换两个元素的函数
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 数组分区函数
static int partitionLeft(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, high);
return i;
}
// 执行随机分区的函数
static int partitionRight(int[] arr, int low, int high) {
Random rand = new Random();
int r = low + rand.nextInt(high - low);
swap(arr, r, high);
return partitionLeft(arr, low, high);
}
// 快速排序的递归函数
static void quicksort(int[] arr, int low, int high) {
if (low < high) {
int p = partitionRight(arr, low, high);
quicksort(arr, low, p - 1);
quicksort(arr, p + 1, high);
}
}
// 打印数组的函数
static void printArray(int[] arr) {
for (int element : arr) {
System.out.print(element + " ");
}
System.out.println();
}
// 驱动代码
public static void main(String[] args) {
int[] arr = {6, 4, 12, 8, 15, 16};
int n = arr.length;
System.out.print("原始数组： ");
printArray(arr);
quicksort(arr, 0, n - 1);
System.out.print("排序数组： ");
printArray(arr);
}
}
输出
原始数组： 6 4 12 8 15 16 排序数组： 4 6 8 12 15 16
import random
# 数组分区函数
def partition_left(arr, low, high):
pivot = arr[high]
i = low
for j in range(low, high):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i
# 执行随机分区的函数
def partition_right(arr, low, high):
r = random.randint(low, high)
arr[r], arr[high] = arr[high], arr[r]
return partition_left(arr, low, high)
# 快速排序的递归函数
def quicksort(arr, low, high):
if low < high:
p = partition_right(arr, low, high)
quicksort(arr, low, p - 1)
quicksort(arr, p + 1, high)
# 打印数组的函数
def printArray(arr):
for element in arr:
print(element, end=" ")
print()
# 驱动代码
arr = [6, 4, 12, 8, 15, 16]
n = len(arr)
print("原始数组：", end=" ")
printArray(arr)
quicksort(arr, 0, n - 1)
print("排序数组：", end=" ")
printArray(arr)
输出
原始数组： 6 4 12 8 15 16 排序数组： 4 6 8 12 15 16
