python排序算法-（4）快速排序
快速排序是一種高效的排序算法，它的時間復雜度為 O(nlogn)。快速排序算法的基本思想是：通過一趟排序將待排序數組分成兩部分，其中一部分中的所有元素都小于另一部分中的所有元素，然后再分別對兩部分進行遞歸排序，最終即可完成整個數組的排序。
具體來說，快速排序算法的實現過程如下：
1. 首先，從數列中挑出一個元素作為基準元素(通常選取數列的最后一個元素或者隨機一個元素作為基準元素)；
2. 接著，把數列中所有小于基準元素的元素放在基準元素前面，把所有大于基準元素的元素放在基準元素后面(相等的元素可以放在任意一邊)。這個過程稱為分區(qū)操作(partition)；
3. 對左右兩個分區(qū)分別遞歸地進行快速排序。
4. 當分區(qū)只剩下一個或沒有元素時，遞歸結束。
通過不斷進行分區(qū)操作和遞歸調用，快速排序算法可以將未排序的數組或子數組進行排序。由于其時間復雜度優(yōu)秀，在實際應用中得到廣泛的使用。
import random
# 尋找分區(qū)位置的函數
def partition(array, low, high):
? ?# 選擇最右邊的元素作為樞軸
? ?pivot = array[high]
? ?# 若要使用隨機樞軸，請取消關注下面3行的注釋：
? ?######################################################################
? ?# piv_index=random.randrange(low, high)
? ?# pivot = array[piv_index]
? ?# (array[high], array[piv_index]) = (array[piv_index], array[high])
? ?######################################################################
? ?# 指針 i
? ?i = low - 1
? ?# 遍歷所有元素
? ?# 將每個元素與樞軸比較
? ?for j in range(low, high):
? ? ? ?if array[j] <= pivot:
? ? ? ? ? ?# 如果尋找到小于樞軸的元素，則將它與索引 i + 1 處的元素交換
? ? ? ? ? ?i = i + 1
? ? ? ? ? ?# 交換 i 和 j 處的元素
? ? ? ? ? ?(array[i], array[j]) = (array[j], array[i])
? ?# 將樞軸元素與指定索引 i + 1 處的元素交換
? ?(array[i + 1], array[high]) = (array[high], array[i + 1])
? ?# 返回樞軸元素的索引位置
? ?return i + 1
# 快速排序函數
def quickSort(array, low, high):
? ?if low < high:
? ? ? ?# 調用 partition 函數獲取樞軸元素的索引位置
? ? ? ?pi = partition(array, low, high)
? ? ? ?# 對樞軸元素左側的子數組遞歸進行排序
? ? ? ?quickSort(array, low, pi - 1)
? ? ? ?# 對樞軸元素右側的子數組遞歸進行排序
? ? ? ?quickSort(array, pi + 1, high)
# 測試
array=random.sample(range(0, 100), 50)
print("原始數組為:")
print(array)
size = len(array)
quickSort(array, 0, size-1)
print('快速排序后的數組為:')
print(array)運行環(huán)境：python3.8
原始數組為:
[81, 69, 61, 47, 42, 98, 14, 36, 18, 93, 55, 80, 22, 26, 11, 85, 9, 53, 43, 32, 90, 64, 51, 99, 33, 39, 45, 73, 63, 7, 48, 74, 60, 23, 2, 30, 20, 89, 54, 91, 96, 49, 44, 6, 65, 35, 19, 57, 79, 95]
快速排序后的數組為:
[2, 6, 7, 9, 11, 14, 18, 19, 20, 22, 23, 26, 30, 32, 33, 35, 36, 39, 42, 43, 44, 45, 47, 48, 49, 51, 53, 54, 55, 57, 60, 61, 63, 64, 65, 69, 73, 74, 79, 80, 81, 85, 89, 90, 91, 93, 95, 96, 98, 99]
