随机快速排序算法

Table of content
上一页
下一页

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

随机快速排序旨在降低算法以最坏情况时间复杂度O(n2)执行的可能性。快速排序的最坏情况时间复杂度出现在输入为已排序列表时，导致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。我们需要应用快速排序算法对列表进行排序。

sorted_input_list

步骤1

考虑到可能的最坏情况，如果随机选择的枢纽元素也是最高索引数字，它会比较所有其他数字，并选择另一个枢纽元素。

pivot

由于15大于列表中的所有其他数字，因此不会交换，并且会选择另一个枢纽元素。

步骤2

这次，如果随机枢纽函数选择7作为枢纽数字：

pivot_7

现在，枢纽将列表分成两半，因此通常执行标准快速排序。但是，时间复杂度比最坏情况低。

需要注意的是，快速排序的最坏情况时间复杂度将始终保持O(n2)，但通过随机化，我们降低了该最坏情况的发生率。

实施

以下是上述方法在各种编程语言中的实现：

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("Sorted 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
打印页面
上一页
下一页
广告