快速排序：用Python实现简单高效的数组排序

小蓝 • 2024-11-26 21:08 • 编程

快速排序是一种常用的排序算法之一，也是一种高效的排序方法，尤其擅长对大规模数据集排序。

一、算法原理

快速排序的基本思路是：选择一个基准元素，将数组分为两个子数组，小于基准的位于左子数组，大于基准的位于右子数组，然后递归地对左右子数组进行排序，最后合并两个子数组。

具体的实现方法有很多，我们举一个例子：

<pre>
def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        #选取基准元素
        pivot = array[0]
        #将小于基准的元素放到左边，大于基准的元素放到右边
        left = [x for x in array[1:] if x < pivot]
        right = [x for x in array[1:] if x >= pivot]
        #递归排序左右子数组
        return quick_sort(left) + [pivot] + quick_sort(right)
</pre>

二、算法优化

快速排序的平均时间复杂度为O(nlogn)，是一种非常高效的排序算法。不过，在实际应用中，快排也有一些局限性：

1、如果已经排好序的数组会使递归树的深度达到O(n)，时间复杂度变为O(n^2)。这种情况下，可以随机选取基准元素来避免。

2、在业务上，如果数组中有大量重复的元素，快排的效率会大大降低。这种情况下，可以选择三路快排算法。

我们来看看如何优化快速排序算法：

1、随机选取基准元素

可以通过random模块来随机选取基准元素，代码如下：

<pre>
import random

def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        #随机选取基准元素
        index = random.randint(0, len(array) - 1)
        pivot = array[index]
        #将小于基准的元素放到左边，大于基准的元素放到右边
        left = [x for x in array[:index] + array[index+1:] if x < pivot]
        right = [x for x in array[:index] + array[index+1:] if x >= pivot]
        #递归排序左右子数组
        return quick_sort(left) + [pivot] + quick_sort(right)
</pre>

2、三路快排

三路快排算法是对快速排序算法的一种优化，主要应用于处理有大量重复元素的数组。它不但能减少递归深度，也能减少时间复杂度。

思路是将数组分为小于、等于、大于基准元素的三个区间，然后递归对小于和大于的部分继续进行三路快排，以此类推。

<pre>
def quick_sort_3w(array):
    if len(array) <= 1:
        return array
    else:
        #选取基准元素
        pivot = array[0]
        lt = [x for x in array if x < pivot] #小于基准元素的数组
        eq = [x for x in array if x == pivot] #等于基准元素的数组
        gt = [x for x in array if x > pivot] #大于基准元素的数组
        #递归排序三个子数组
        return quick_sort_3w(lt) + eq + quick_sort_3w(gt)
</pre>

三、算法实现

现在，我们可以来实现一个完整的快速排序算法，在实现过程中可以选择以上两种优化算法。

<pre>
import random

def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        #随机选取基准元素
        index = random.randint(0, len(array) - 1)
        pivot = array[index]
        #将小于基准的元素放到左边，大于基准的元素放到右边
        left = [x for x in array[:index] + array[index+1:] if x < pivot]
        right = [x for x in array[:index] + array[index+1:] if x >= pivot]
        #递归排序左右子数组
        return quick_sort(left) + [pivot] + quick_sort(right)

def quick_sort_3w(array):
    if len(array) <= 1:
        return array
    else:
        #选取基准元素
        pivot = array[0]
        lt = [x for x in array if x < pivot] #小于基准元素的数组
        eq = [x for x in array if x == pivot] #等于基准元素的数组
        gt = [x for x in array if x > pivot] #大于基准元素的数组
        #递归排序三个子数组
        return quick_sort_3w(lt) + eq + quick_sort_3w(gt)
</pre>

四、总结

快速排序是一种常用的高效排序算法，一般情况下优于冒泡排序、插入排序、选择排序等算法。

快速排序的基本思路是分治法，通过递归将数组分为两个子数组进行排序，最后合并。

如果数组中有大量重复元素，可以采用三路快排算法进行优化。

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