设计与分析——随机快速排序

快速排序是一种流行的排序算法，它选择一个主元元素并围绕该主元元素对输入列表进行排序。要了解有关快速排序的更多信息，请单击此处。

随机快速排序旨在减少算法在O(n 2 )最坏情况时间复杂度下执行的机会。当给定的输入是一个已经排序的列表时，快速排序的最坏情况时间复杂度就会出现，导致 n(n – 1) 次比较。有两种方法可以随机化快速排序 -

  • 随机打乱输入：对输入列表进行随机化，使排序后的输入再次打乱，从而降低时间复杂度。然而，这通常不会在随机快速排序中执行。

  • 随机选择主元：将主元设为随机变量是随机快速排序中常用的方法。在这里，即使输入已排序，主元也是随机选择的，因此可以避免最坏情况的时间复杂度。

随机快速排序算法

该算法完全遵循标准算法，只是它随机化了主元选择。

伪代码

partition-left(arr[], low, high)
   pivot = arr[high]
   i = low // place for swapping
   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 作为主元数 -

枢轴_7

现在枢轴将列表分成两半，因此通常会执行标准的快速排序。然而，时间复杂度比最坏情况有所降低。

值得注意的是，快速排序的最坏情况时间复杂度始终保持为O(n 2 )，但通过随机化，我们正在减少最坏情况的出现。

例子

C C++ Java Python 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to swap two elements
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
// Function to partition the array
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;
}
// Function to perform random partition
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);
}
// Recursive function for quicksort
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);
    }
}
// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
// Driver code
int main() {
    int arr[] = { 6, 4, 12, 8, 15, 16};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: ");
    printArray(arr, n);
    quicksort(arr, 0, n - 1);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

输出

Original array: 6 4 12 8 15 16 
Sorted array: 4 6 8 12 15 16

#include <iostream>
#include <cstdlib>
#include <ctime>
// Function to swap two elements
void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
// Function to partition the array
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;
}
// Function to perform random partition
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);
}
// Recursive function for quicksort
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);
    }
}
// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}
// Driver code
int main() {
    int arr[] = {6, 4, 12, 8, 15, 16};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << "Original array: ";
    printArray(arr, n);
    quicksort(arr, 0, n - 1);
    std::cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

输出

Original array: 6 4 12 8 15 16 
Sorted array: 4 6 8 12 15 16 

import java.util.Arrays;
import java.util.Random;
public class QuickSort {
    // Function to swap two elements
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // Function to partition the array
    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;
    }
    // Function to perform random partition
    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);
    }
    // Recursive function for quicksort
    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);
        }
    }
    // Function to print the array
    static void printArray(int[] arr) {
        for (int element : arr) {
            System.out.print(element + " ");
        }
        System.out.println();
    }
    // Driver code
    public static void main(String[] args) {
        int[] arr = {6, 4, 12, 8, 15, 16};
        int n = arr.length;
        System.out.print("Original array: ");
        printArray(arr);
        quicksort(arr, 0, n - 1);
        System.out.print("\nSorted array: ");
        printArray(arr);
    }
}

输出

Original array: 6 4 12 8 15 16 
Sorted array: 4 6 8 12 15 16 

import random
# Function to partition the array
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
# Function to perform random partition
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)
# Recursive function for quicksort
def quicksort(arr, low, high):
    if low < high:
        p = partition_right(arr, low, high)
        quicksort(arr, low, p - 1)
        quicksort(arr, p + 1, high)
# Function to print the array
def printArray(arr):
    for element in arr:
        print(element, end=" ")
    print()
# Driver code
arr = [6, 4, 12, 8, 15, 16]
n = len(arr)
print("Original array:", end=" ")
printArray(arr)
quicksort(arr, 0, n - 1)
print("Sorted array:", end=" ")
printArray(arr)

输出

Original array: 6 4 12 8 15 16 
Sorted array: 4 6 8 12 15 16