在 Python 中快速排序
-
在 Python 中使用
numpy.sort()方法進行快速排序 -
在 Python 中使用
pandas庫的Series.sort_values()方法進行快速排序 - 在 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