使用 Python 进行随机枢轴的快速排序

2024 年 8 月 29 日 | 阅读 3 分钟

引言

排序是计算机科学中的一项核心操作，其应用从信息检索到提高算法执行效率。在各种排序算法中，快速排序以其速度和效率而闻名。然而，快速排序的有效性在很大程度上取决于主元元素的选取。在本文中，我们将深入探讨快速排序的概念，并研究一种重要的改进：使用随机选取主元的快速排序。

理解快速排序

快速排序是一种著名且高效的排序算法，遵循“分而治之”的范式。它通过从数组中选择一个主元元素，并将数组划分为两个子数组：小于主元的元素和大于主元的元素。这个过程递归地在子数组上进行，直到整个数组被排序。

快速排序中的主元确定

主元元素的选取在快速排序的效率中起着至关重要的作用。在最坏的情况下，当主元总是选择不当时，快速排序的效率会退化为二次时间复杂度算法，使其效率低下。为了解决这个挑战，我们引入了随机选取主元的概念。

随机选取主元策略

快速排序中的随机选取主元包括从数组中随机选择主元元素。与选择第一个或最后一个元素作为主元的传统主元确定技术不同，随机选取主元确保了主元的选择是不可预测的。这种随机性是缓解最坏情况的关键。主元元素的选取极大地影响了快速排序的性能。传统的快速排序实现通常选择第一个或最后一个元素作为主元。然而，这种方法在某些情况下可能会导致失败，例如当输入数据已排序时。这就是随机选取主元的作用所在。

算法

function quicksort(arr, low, high):
    if low < high:
        # Randomly select a pivot element
        pivot_index = randomly_select_pivot(arr, low, high)
        
        # Partition the array around the pivot and get the pivot's final position
        pivot_position = partition(arr, low, high, pivot_index)
        
        # Recursively sort the subarrays on both sides of the pivot
        quicksort(arr, low, pivot_position - 1)
        quicksort(arr, pivot_position + 1, high)

function randomly_select_pivot(arr, low, high):
    # Generate a random index between low and high
    pivot_index = random(low, high)
    return pivot_index

function partition(arr, low, high, pivot_index):
    # Swap the pivot element with the last element to simplify partitioning
    swap(arr[pivot_index], arr[high])
    pivot = arr[high]
    
    i = low  # Initialize the index for the smaller element
    
    for j = low to high - 1:
        if arr[j] <= pivot:
            # Swap arr[i] and arr[j] if the current element is smaller than or equal to the pivot
            swap(arr[i], arr[j])
            i = i + 1
    
    # Swap arr[i] and arr[high] to place the pivot in its final position
    swap(arr[i], arr[high])
    
    return i  # Return the index of the pivot element

function swap(a, b):
    # Helper function to swap two elements in an array
    temp = a
    a = b
    b = temp

Python 实现

代码

import random

def quicksort(arr):
    # Base case: If the array has 1 or fewer elements, it's already sorted.
    if len(arr) <= 1:
        return arr

    # Randomly select a pivot element
    pivot_index = random.randint(0, len(arr) - 1)
    pivot = arr[pivot_index]

    # Partition the array into three subarrays: lesser, equal, and greater than the pivot
    lesser = []
    equal = []
    greater = []

    for element in arr:
        if element < pivot:
            lesser.append(element)
        elif element == pivot:
            equal.append(element)
        else:
            greater.append(element)

    # Recursively sort the lesser and greater subarrays and combine them with the equal elements
    return quicksort(lesser) + equal + quicksort(greater)

if __name__ == "__main__":
    # Example usage:
    arr = [3, 6, 8, 10, 1, 2, 1]
    
    # Call the quicksort function to sort the array
    sorted_arr = quicksort(arr)
    
    # Display the original and sorted arrays
    print("Original array:", arr)
    print("Sorted array:", sorted_arr)

输出

Original array: [3, 6, 8, 10, 1, 2, 1]
Sorted array: [1, 1, 2, 3, 6, 8, 10]

结论

总而言之，带有随机选取主元的快速排序是一种强大的排序方法，具有多种划分选择，其中 Lomuto 和 Hoare 是两个显著的选择。这两种方法都利用了主元选择的随机性来提高快速排序在不同数据场景下的性能和适应性。提供的 Python 程序以及详细的注释，为有兴趣探索和实现这些算法的开发人员提供了一个全面的资源。

下一个主题从 Python 使用 Bioconductor

使用 Python 进行随机枢轴的快速排序

引言

理解快速排序

快速排序中的主元确定

随机选取主元策略

算法

Python 实现

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

使用 Python 进行随机枢轴的快速排序

引言

理解快速排序

快速排序中的主元确定

随机选取主元策略

算法

Python 实现

结论

相关帖子

使用 SQLAlchemy 更新 JSONB 列中的单个元素

使用 Python 生成吸引人的二维码

如何在 Python 中使用 pass 语句

Python 中的 Getter 和 Setter

使用 Python 查找具有相同概率的最大出现元素索引

Python 中的模块 vs 函数

Python - 合并文件夹中的所有 CSV 文件

Python NetworkX

Python 中的 Lee 算法

Python IPaddress 模块

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器