【常見算法Python描述】快速排序空間與時間複雜度優化

文章目錄

• 一、快速排序空間複雜度優化
• • 1. 原地快速排序簡介
  • 2. 原地快速排序詳解
  • 3. 原地快速排序實作
• 二、快速排序時間複雜度優化
• • 1. 随機化快速排序簡介
  • 2. 随機化快速排序實作
  • 3. 随機化快速排序時間複雜度

通過【常見算法Python描述】基于分治思想的快速排序簡介與實作，我們介紹了快速排序，并對通過鍊式隊列形式給出的待排序列以及通過清單形式給出的待排序列應用了快速排序，雖然二者都具有較為直覺的優點，但這兩種實作的空間複雜度較高，因為每一次遞歸都需要額外建立（雙端）隊列對象作為容器分别儲存大于、等于、小于基準值的元素。針對該問題，本文将在待排序列為清單時，對其進行空間效率更高的快速排序，即原地快速排序。

另一個問題是，當固定選取序列的某一個元素作為基準值時，例如選擇（子）序列的最後一個元素作為基準值，如果此時待排序列已經有序或基本有序，那麼遞歸調用的深度就會和待排序列元素個數相近，這會導緻 O ( n 2 ) O(n^2) O(n2)的時間複雜度。針對該問題，本文将介紹如何通過随機選取（子）序列的元素作為基準值，使得對任意給定序列進行快速排序的期望時間複雜度都是 O ( n l o g n ) O(nlogn) O(nlogn)，即随機化快速排序。

一、快速排序空間複雜度優化

1. 原地快速排序簡介

原地快速排序中的原地的含義是指，除了待排序列所占用的記憶體空間外，在算法的執行過程中僅需少量用于程式正常運作（如遞歸調用狀态保持，計數變量）的記憶體。當給定待排序列為清單，且每次選擇待排（子）序列的最後一個元素作為基準值時，對其進行原地快速排序的流程如下：

• 分：将（子）序列

  arr[p:r]

  分為兩個子序列

  arr[p:q - 1]

  、

  arr[q + 1:r]

  ，且：

  • arr[p:q - 1]

    中的元素均小于或等于

    arr[q]

    ；

  • arr[q + 1:r]

    中的元素均大于

    arr[q]

    ，且此過程會計算出索引

    q

    的值；
• 治：對兩個子序列

  arr[p:q - 1]

  、

  arr[q + 1:r]

  分别進行遞歸調用；
• 合：因為分和治的操作均在待排序列上進行，前面兩步完成後

  arr[p:r]

  一定有序。

上述步驟使用僞代碼描述如下：

quick_sort(arr, p, r):
	if p < r:
		q = partition(arr, p, r)
		quick_sort(arr, p, q - 1)
		quick_sort(arr, q + 1, r)
           

如果要對整個待排序列進行原地快速排序，則應該按照

quick_sort(arr, 1, arr.length)

進行調用。

通過上述僞代碼我們知道，最重要在于如何實作

partition

函數，該方法決定了如何能在待排（子）序列的空間基礎上将其分為兩個滿足要求的子序列

arr[p:q - 1]

和

arr[q + 1:r]

，且傳回

q

的值。下面為該方法的僞代碼：

partition(arr, p, r):
	x = arr[r]
	i = p - 1
	for j = p to r - 1:
		if arr[j] <= x:
			i = i + 1
			swap arr[i], arr[j]
	swap arr[i + 1], arr[r]
	return i + 1
           

2. 原地快速排序詳解

為便于了解，下圖是對元素數量為8的待排序列第一次調用

partition

函數的過程，且對圖示的各種顔色做如下約定：

• 淺色單元表示在本次遞歸調用過程中不大于基準值的元素及其位置；
• 淺色單元表示在本次遞歸調用過程中大于基準值的元素及其位置；
• 無色單元表示在本次遞歸調用過程中還未與基準值進行比較的元素及其位置，或者表示基準值及其初始位置。

通過上述流程我們可以看出，在

partition

函數調用過程中，每一次循環疊代後，待排序列的元素都可大緻被分為如下圖所示的四個部分（某些階段一些部分可能為空），即對任何位于待排（子）序列元素索引下限

p

和上限

r

之間的索引

k

，都有：

• 如果

  p <= k <= i

  ，則

  arr[k] <= x

  ；
• 如果

  i + 1 <= k <= j - 1

  ，則

  arr[k] > x

  ；
• 如果

  j <= k <= r - 1

  ，

  arr[k]

  和

  x

  之間的大小關系還未确定；
• 如果

  k = r

  ，則

  arr[k] = x

  。

在

partition

函數執行過程中，需要注意的兩點是：

• 每一次疊代過程中，根據

  if

  條件的判斷結果，其執行情況完全可以分為下圖兩種情況，即：
  • 如果

    arr[j] > x

    ，則本次疊代即結束，即大于基準值的元素自然地位于元素均大于基準值的子序列中；
  • 如果

    arr[j] <= x

    ，則索引

    i

    遞增，再交換

    arr[i]

    和

    arr[j]

    ，這可以使得小于基準值的元素被交換至元素均不大于基準值的子序列中，最後本次疊代結束；
• 對于

  partition

  函數的最後兩行：
  • 一方面将基準值和所有元素均大于基準值的子序列中的最左側元素進行了交換，這成功實作了該基準值将待排（子）序列分為滿足條件的兩個子序列；
  • 另一方面還傳回了基準值的索引，則在後續遞歸地對兩個子序列調用

    partition

    函數時可以分别用于确定二者的索引上限和下限。

3. 原地快速排序實作

通過上述分析，在待排序列為清單時候，下面可以很容易得到原地快速排序的Python實作：

def partition(arr, p, r):
    """子序列劃分"""
    pivot = arr[r]
    i = p - 1  # 記錄元素均不大于pivot的子序列中最右側元素的索引上界
    for j in range(p, r):
        if arr[j] <= pivot:
            i += 1  # 元素均不大于pivot的子序列，元素索引上界右移
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    return i + 1


def inplace_quick_sort(arr, p, r):
    """針對清單的原地快速排序實作"""
    if p < r:
        q = partition(arr, p, r)
        inplace_quick_sort(arr, p, q - 1)
        inplace_quick_sort(arr, q + 1, r)


arr = [23, 13, 45, 16, 32, 56, 98, 11]
inplace_quick_sort(arr, 0, len(arr) - 1)
print(arr)  # [11, 13, 16, 23, 32, 45, 56, 98]
           

二、快速排序時間複雜度優化

快速排序的效率高低取決于在将待排序列分為兩個子序列時，二者的元素個數是否盡可能相等，這裡就将介紹一種對這一步驟進行改善的快速排序變形——随機化快速排序，以確定給定任何待排序列的情況下，快速排序都可以保證 O ( n l o g n ) O(nlogn) O(nlogn)的期望時間複雜度。

1. 随機化快速排序簡介

随機快速排序的思想很簡單，即每一次從待排（子）序列中随機選擇一個元素作為基準值而非固定使用某一個位置（如第一個或最後一個位置）的元素作為基準值，除此之外其他任何步驟和普通快速排序算法保持一緻。

2. 随機化快速排序實作

下面是在對上述原地快速排序進行修改後得到的随機化快速排序實作，實際上，我們隻需要封裝一個

randomized_partition

函數，在其中調用上述

partition

函數之前展現随機化的操作即可：

from random import randint


def partition(arr, p, r):
    """子序列劃分"""
    pivot = arr[r]
    i = p - 1  # 記錄元素均不大于pivot的子序列中最右側元素的索引上界
    for j in range(p, r):
        if arr[j] <= pivot:
            i += 1  # 元素均不大于pivot的子序列，元素索引上界右移
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    return i + 1


def randomized_partition(arr, p, r):
    """随機選擇元素作為基準值後進行子序列劃分"""
    i = randint(p, r)
    arr[i], arr[r] = arr[r], arr[i]
    return partition(arr, p, r)


def randomized_quick_sort(arr, p, r):
    if p < r:
        q = randomized_partition(arr, p, r)
        randomized_quick_sort(arr, p, q - 1)
        randomized_quick_sort(arr, q + 1, r)


arr = [23, 13, 45, 16, 32, 56, 98, 11]
randomized_quick_sort(arr, 0, len(arr) - 1)
print(arr)  # [11, 13, 16, 23, 32, 45, 56, 98]
           

3. 随機化快速排序時間複雜度

對于元素數量為 n n n的待排序列，對其使用随機化快速排序的期望時間複雜度為 O ( n l o g n ) O(nlogn) O(nlogn)。

從直覺上來看，當随機選擇基準值時，其期望時間複雜度不會低于普通快速排序的平均時間複雜度，因為有理由相信在較高的機率下該基準值會将（子）序列劃分成元素個數相近的兩個子序列，是以這種情況下其期望的時間複雜度為 O ( n l o g n ) O(nlogn) O(nlogn)。