Python排序算法：快速实现数据集排序

小蓝 • 2024-12-07 17:49 • 编程

在现代计算机领域中，排序算法是非常重要的一种基础算法。排序算法是将一组无序的元素以某种规则按相应的顺序排列的过程。快速排序算法是一种相对高效的排序方法，可以在O(NlogN)的时间复杂度内完成排序，但是在处理大型数据集时比较吃紧，因为它的空间复杂度为O(N)，而N值较大时，空间开销会变得很大。

一、快速排序算法概述

快速排序算法是一种排序方式，选定一个基准（pivot）值，按照基准值将元素分成两个子序列，其中一个序列比基准值小，一个序列比基准值大，然后递归地继续进行排序，最后将两个子序列合并成一个有序序列。

二、快速排序算法实现

下面是一个实现快速排序算法的Python示例代码：

def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i  pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

array = [56, 23, 89, 11, 7, 35, 12, 5, 67]
sorted_array = quick_sort(array)
print(sorted_array)

在上面的代码中，我们首先检查数组是否只有一个或零个元素，如果是，直接返回数组。然后选取数组中的第一个元素作为基准，将小于等于基准的元素放在一个列表中，将大于基准的元素放在另一个列表中，最后递归地调用quick_sort()函数对两个子序列进行排序，并将它们与基准值拼接在一起，返回一个有序的数组。

三、快速排序算法优化

1、选择更优的基准

快速排序的时间复杂度是由选择基准的方式所决定的。如果选取的基准恰好是数组中最小（或最大）的值，那么快速排序算法的复杂度将达到O(N²)。因此，可以通过随机选取基准的方式来避免这种情况的发生，或者通过取数组中三个数的中位数作为基准，来确保分割较为平均，从而达到更优的效果。

下面是一个随机选取基准的Python代码示例：

import random

def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        # 随机选取基准
        index = random.randint(0, len(array)-1)
        pivot = array[index]
        less = [i for i in array[:index]+array[index+1:] if i  pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

array = [56, 23, 89, 11, 7, 35, 12, 5, 67]
sorted_array = quick_sort(array)
print(sorted_array)

2、优化递归深度

在大型数据集上运行快速排序算法时，递归深度可能会非常大，而Python的默认递归深度是1000，如果超过这个深度，会引发递归调用栈溢出的异常。为了解决这种问题，可以通过使用非递归的实现方式，或者使用尾递归的方式来进行优化。

下面是一个尾递归实现方式的Python代码示例：

def quick_sort(array, left=0, right=None):
    if right is None:
        right = len(array) - 1
    if left >= right:
        return
    pivot = array[left]
    i, j = left, right
    while i < j:
        while i  pivot:
            j -= 1
        array[i] = array[j]
        while i < j and array[i] <= pivot:
            i += 1
        array[j] = array[i]
    array[i] = pivot
    quick_sort(array, left, i - 1)
    quick_sort(array, i + 1, right)

array = [56, 23, 89, 11, 7, 35, 12, 5, 67]
quick_sort(array)
print(array)

在上面的代码中，我们首先将left和right作为参数传递给quick_sort()函数，并将right的默认值设置为数组长度-1。然后我们遍历数组，选取array[left]作为基准，将i和j初始化为left和right，对整个数组进行遍历，将比基准大的元素移动到右边，比基准小的元素移动到左边。最后我们对左右两边的子序列进行递归调用，并将结果拼接在一起，得到最终的有序数组。

四、总结

快速排序算法是一个非常有效的排序算法，它的时间复杂度是O(NlogN)，但是也需要注意到它的空间开销。如果使用随机选取基准和尾递归的方式进行优化，可以使得快速排序算法在处理大型数据集时更为高效。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/206073.html