在 Python 中快速排序

Muhammad Waiz Khan 2023年1月30日 2021年2月28日
  1. 在 Python 中使用 numpy.sort() 方法進行快速排序
  2. 在 Python 中使用 pandas 庫的 Series.sort_values() 方法進行快速排序
  3. 在 Python 中快速排序的實現
在 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

相關文章 - Python Sort