Python 中 Hoare 的 vs. Lomuto 分区方案在 QuickSort 中的应用

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

排序是计算机科学中的一项主要活动，而 QuickSort 由于这个原因是一个极其高效的算法。本文将探讨 QuickSort 的概念，包括 Python 中的随机枢轴选择。我们将从 QuickSort 的介绍开始，深入探讨其关键组成部分。

什么是 QuickSort？

QuickSort 是一种著名的排序算法，属于基于比较的排序类别。它由 Tony Hoare 于 1960 年创建，以其速度和简洁性而闻名。它的工作原理是选择数组中的一个“枢轴”元素，并将其他元素分成两个子数组：小于枢轴的元素和大于枢轴的元素。然后递归地将该过程应用于子数组，直到整个数组排序完毕。

随机枢轴选择

枢轴元素的选取对 QuickSort 的性能影响极大。传统的 QuickSort 实现经常选择第一个或最后一个元素作为枢轴。但是，在某些情况下，例如输入数据已排序时，这种方法可能导致性能下降。这就是随机枢轴选择发挥作用的地方。

使用 Hoare 分区进行随机枢轴选择

Hoare 分区是 QuickSort 的一种替代分区方案，与 Lomuto 分区相比，它在交换方面效率更高。以下是一个使用 Hoare 分区和随机枢轴选择实现 QuickSort 的 Python 程序。

算法

从数组中选择一个枢轴元素。在这种情况下，我们将第一个元素用作枢轴。
初始化两个指针 i 和 j，i 指向数组的第一个元素，j 指向数组的最后一个元素。
递增 i，直到找到一个大于或等于枢轴的元素。
递减 j，直到找到一个小于或等于枢轴的元素。
如果 i 不等于 j，则交换 i 和 j 处的元素。继续此过程，直到 i 大于 j。
当 i 大于 j 时，表示枢轴已到达其正确位置。将枢轴元素与索引 j 处的元素交换。
递归地将 QuickSort 应用于枢轴左侧的子数组（小于枢轴的元素）和枢轴右侧的子数组（大于枢轴的元素）。
重复此过程，直到整个数组排序完毕。

代码

# Python program for Random Pivoting using Hoare Partitioning
import random

# Define the QuickSort function using Hoare Partitioning.
def quicksort_hoare(arr, low, high):
    # Base case: If the range is invalid or contains only one element, it's already sorted.
    if low < high:
        # Randomly select a pivot element within the specified range.
        pivot_index = random.randint(low, high)
        # Swap the pivot element with the first element.
        arr[pivot_index], arr[low] = arr[low], arr[pivot_index]
        pivot = arr[low]

        i = low - 1
        j = high + 1
        while True:
            i += 1
            while arr[i] < pivot:
                i += 1

            j -= 1
            while arr[j] > pivot:
                j -= 1

            if i >= j:
                break

            arr[i], arr[j] = arr[j], arr[i]

        pivot_index = j
        # Recursively sorts the subarrays to the left and right of the pivot element.
        quicksort_hoare(arr, low, pivot_index)
        quicksort_hoare(arr, pivot_index + 1, high)

my_list = [3, 6, 8, 10, 1, 2, 1]
print(" Original Array : ", my_list)
# Call the QuickSort function with the input list.
quicksort_hoare(my_list, 0, len(my_list) - 1)
# Printing the sorted list.
print("Sorted Array based on Hoare Partitioning : ", my_list)

输出

Original Array : [3, 6, 8, 10, 1, 2, 1]
Sorted Array based on Hoare Partitioning : [1, 1, 2, 3, 6, 8, 10]

时间复杂度：使用 Hoare 分区的 QuickSort 的平均时间复杂度为 O(n log n)，最坏情况时间复杂度为 O(n^2)。

空间复杂度：由于递归函数调用和使用的堆栈空间，空间复杂度为 O(log n)，其中 'n' 是数据数组中的元素数量。

使用 Lomuto 分区进行随机枢轴选择

随机枢轴选择涉及选择一个随机元素作为枢轴。这种随机性降低了遇到最坏情况的可能性，并确保 QuickSort 在各种数据分布下都具有效率。以下是一个使用 Lomuto 分区和随机枢轴选择实现 QuickSort 的 Python 程序。

算法

从数组中选择一个枢轴元素。在这种情况下，我们将最后一个元素用作枢轴。
将两个指针 i 和 j 初始化为数组的第一个元素。
递增 j，直到找到一个大于或等于枢轴的元素。
递减 i，直到找到一个小于或等于枢轴的元素。
如果 i 不等于 j，则交换 i 和 j 处的元素。继续此过程，直到 i 大于 j。
将枢轴元素与索引 i 处的元素交换，将枢轴放置在其在排序数组中的正确位置。
递归地将 QuickSort 应用于枢轴左侧的子数组和枢轴右侧的子数组（大于枢轴的元素）。
重复此过程，直到整个数组排序完毕。

代码

# Python program for Random Pivoting using Lomuto Partitioning
import random

# Define the QuickSort function using Lomuto Partitioning.
def quicksort_lomuto(arr, low, high):
    # Base case: If the range is invalid or contains only one element, it's already sorted.
    if low < high:
        # Randomly select a pivot element within the specified range.
        pivot_index = random.randint(low, high)
        # Swap the pivot element with the last element.
        arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
        pivot = arr[high]

        i = low - 1
        for j in range(low, high):
            if arr[j] < pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]

        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        pivot_index = i + 1

        # Recursively sort the subarrays to the left and right of the pivot.
        quicksort_lomuto(arr, low, pivot_index - 1)
        quicksort_lomuto(arr, pivot_index + 1, high)

my_list = [3, 6, 8, 10, 1, 2, 1]
print(" Original Array: ", my_list)
# Call the QuickSort function with the input list.
quicksort_lomuto(my_list, 0, len(my_list) - 1)
# Print the sorted list.
print(" Sorted Array based on Lomuto Partitioning : ", my_list)

输出

Original Array : [3, 6, 8, 10, 1, 2, 1]
Sorted Array based on Lomuto Partitioning : [1, 1, 2, 3, 6, 8, 10]

时间复杂度：使用 Lomuto 分区的 QuickSort 的最坏情况时间复杂度为 O(n^2)，平均时间复杂度为 O(n log n)，最佳情况时间复杂度为 O(n log n)。

空间复杂度：此实现的内存复杂度为 O(n)，因为递归函数调用，其中 'n' 是数据数组中的元素数量。

比较

Lomuto 分区由于其简单性而更易于实现和理解。Lomuto 分区是稳定的，这意味着它保留了相等元素的相对顺序。Lomuto 分区比 Hoare 分区需要更多的交换，因此在内存操作方面效率较低。通常，它的性能比 Hoare 分区稍慢。

Hoare 分区在时间和交换方面效率更高，因此在实践中更快。Hoare 分区不稳定，可能会改变相等元素的顺序。与 Lomuto 分区相比，Hoare 分区的理解和实现更为复杂。

区别	QuickSort (Lomuto)	QuickSort (Hoare)
性能	Lomuto 分区速度稍慢。	Hoare 分区速度稍快。
稳定性	稳定的 Lomuto 分区	Hoare 分区不稳定。
简单性	实现 Lomuto 分区更简单。	Hoare 分区更难。
掉期（Swaps）	Lomuto 分区需要更多交换	Hoare 分区需要更少的交换
时间复杂度（最坏情况）	两者最坏情况时间复杂度均为 O(n^2)	两者最坏情况时间复杂度相同，均为 O(n^2)
时间复杂度（平均情况）	两者平均时间复杂度均为 O(n log n)	两者平均时间复杂度相同，均为 O(n log n)
时间复杂度（最佳情况）	两者最佳情况时间复杂度均为 O(n log n)	两者最佳情况时间复杂度相同，均为 O(n log n)
空间复杂度	Lomuto 分区的内存复杂度为 O(n)	Hoare 分区的内存复杂度为 O(log n)
用例	Lomuto 分区适用于所有类型的排序。	对于需要高效率的排序，Hoare 分区更可取。
适应性	Lomuto 分区适用于各种数据分布	Hoare 分区最适合更平衡的数据

结论

总之，具有随机枢轴选择的 QuickSort 是一种强大的排序方法，具有多种分区选择，其中 Lomuto 和 Hoare 是两个明显的选择。这两种方法都利用了枢轴选择的随机性来提高 QuickSort 在各种数据场景下的性能和适应性。提供的 Python 程序以及详细的注释，为有兴趣在项目中探索和实现这些算法的人们提供了一个全面的资源。

下一主题Tkinter 中的 iconphoto() 方法 | Python

Python 中 Hoare 的 vs. Lomuto 分区方案在 QuickSort 中的应用

什么是 QuickSort？

随机枢轴选择

使用 Hoare 分区进行随机枢轴选择

使用 Lomuto 分区进行随机枢轴选择

比较

结论

联系信息

关注我们

教程

面试题

在线编译器

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 中 Hoare 的 vs. Lomuto 分区方案在 QuickSort 中的应用

什么是 QuickSort？

随机枢轴选择

使用 Hoare 分区进行随机枢轴选择

使用 Lomuto 分区进行随机枢轴选择

比较

结论

相关帖子

Python 程序将十六进制字符串转换为十进制字符串

查找排序数组中元素的第一个和最后一个位置

Python 中的自动化交易

何时在 Python 中使用省略号

Pandas：使用 read_clipboard() 将剪贴板内容获取为 DataFrame

使用正则表达式验证银行账号

C vs C++ vs Python vs Java

Python 中的跳转语句 - continue 语句

如何从 Python 中提取 YouTube 数据

网络安全中的人工智能：算法对抗算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器