在 Python 中快速排序

1. 在 Python 中使用 numpy.sort() 方法进行快速排序
2. 在 Python 中使用 pandas 库的 Series.sort_values() 方法进行快速排序
3. 在 Python 中快速排序的实现

本教程将解释如何在 Python 中实现和应用快速排序算法。

快速排序算法是一种分而治之的算法。快速排序从数组中选取一个元素作为枢轴，然后将小于枢轴的元素放在一个数组中，而大于枢轴的元素放在另一个数组中，从而将数组围绕所选枢轴分割成子数组。如果数组中包含重复的元素，那么根据算法的实现，可以将等于枢轴的元素放在第三个子数组中，或者放在两个子数组中的任何一个。快速排序通过递归调用对子数组进行排序，对数组进行排序。

由于快速排序算法是通过比较元素来排序的，所以它属于比较排序算法。

在 Python 中使用 numpy.sort() 方法进行快速排序

numpy.sort(array, axis, kind) 方法将一个数组作为输入，并将输入数组的排序副本作为输出。array 参数是我们要排序的数组，axis 是我们要对数组进行排序的沿线，kind 指定了该方法对数组进行排序的算法，其默认值是 quicksort。

下面的示例代码演示了如何在 Python 中使用 numpy.sort() 方法对数组进行快速排序。

import numpy as np

a = np.array([2,3,6,5,7,8,3,1])

sorted_a = np.sort(a, kind='quicksort')
print(sorted_a)

输出：

[1 2 3 3 5 6 7 8]

在 Python 中使用 pandas 库的 Series.sort_values() 方法进行快速排序

Pandas 库的 Series.sort_values(ascending, inplace, kind) 方法将 Pandas Series 作为输入，并返回排序后的系列。

ascending 参数的默认值是 True，所以该方法按照升序对系列进行排序。如果设置为 False，则会按照降序对 Series 进行排序。如果 inplace 参数设置为 True，则将在原始系列中进行更改；否则，将返回输入的排序副本。kind 参数决定使用哪种算法方法对系列进行排序，该方法默认使用快速排序算法。

下面的示例代码演示了如何在 Python 中使用 Series.sortvalues() 对 Series 进行排序：

import pandas as pd

s = pd.Series([1,2,4,2,7,5,3,2,6,8])

s.sort_values(inplace=True, kind='quicksort')
print(s)

输出：

0    1
1    2
3    2
7    2
6    3
2    4
5    5
8    6
4    7
9    8
dtype: int64

在 Python 中快速排序的实现

第三种方法可以是我们自己用 Python 实现快速排序算法。

下面的快速排序的代码实现将数组分为 3 个子数组，一个子数组包含小于中枢的元素，一个子数组包含大于中枢的元素，第三个子数组包含等于中枢的元素。

在每次调用该方法时，我们都会得到 pivot 的排序位置，因为我们是将小于和大于 pivot 的值分开。并通过递归调用将得到完整的排序数组。

下面的示例代码演示了如何用 Python 实现上面解释的快速排序算法。

def sort(array):

    left = []
    equal = []
    right = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                left.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)

        return sort(left) + equal + sort(greater) #recursive calling of the sort() function
    
    else:  # return the array, when it contains only 1 element
        return array