【常見算法Python描述】計數排序、基數排序、桶排序簡介及實作

文章目錄

• 一、計數排序
• • 1. 簡介
  • 2. 僞代碼
  • 3. 圖解
  • 4. 代碼實作
  • 5. 時間複雜度
• 二、基數排序
• • 1. 簡介
  • 2. 代碼實作
  • 3. 時間複雜度
• 三、桶排序
• • 1. 簡介
  • 2. 實作
  • 3. 時間複雜度

一、計數排序

1. 簡介

計數排序假定待排序列中的元素在 0 0 0到 k k k的範圍内，且如果 k = O ( n ) k=O(n) k=O(n)則計算排序的最壞時間複雜度為 Θ ( n ) \Theta(n) Θ(n)。

計數排序的思想在于，對待排序列中的每一個元素 x x x，确定比 x x x小的元素個數，而後利用該資訊直接将元素 x x x放到輸出序列的對應位置。例如：如果有 17 17 17個元素小于 x x x，則 x x x為輸出序列的第18個元素。

然而，實際中需要對上述方案做一定的修改，因為一般輸出序列的一個位置處隻有一個元素，而如果待排序列有多個相同元素，則此時上述方案無法處理這種情形。

2. 僞代碼

下面給出計數排序的僞代碼，其中：假定輸入的待排序列為清單

A[1..n]

，是以

A.length = n

，

B[1..n]

為輸出的有序序列，

C[0..k]

為輔助清單。

counting_sort(A, B, k):
	let C[0..k] be a new array
	for i = 0 to k:
		C[i] = 0
	for j = 1 to A.length:
		C[A[j]] = C[A[j]] + 1
	// 至此，C[i]包含了值等于i的元素個數
	for i = 1 to k:
		C[i] = C[i] + C[i - 1]
	// 至此，C[i]包含了值小于等于i的元素個數
	for j = A.length downto 1:
		B[C[A[j]]] = A[j]
		C[A[j]] = C[A[j]] - 1
           

對于上述

counting_sort

算法，更具體地：

• 第3至4行的

  for

  循環将序列

  C

  的所有元素初始化為0；
• 第5至6行的

  for

  循環每疊代一次都将

  C[i]

  加1，是以該

  for

  循環結束後，對于每一個 i i i（其中 i = 0 , 1 , ⋅ ⋅ ⋅ , k i=0,1,\cdot\cdot\cdot,k i=0,1,⋅⋅⋅,k），

  C[i]

  為

  A

  中等于 i i i的元素個數；
• 第8至9行的

  for

  循環結束後，

  C[i]

  為

  A

  中小于或等于 i i i的元素個數；
• 第11值13行的

  for

  循環将每一個元素

  A[j]

  放置到輸出的有序序列的正确位置，具體地：
  • 如果待排序列

    A

    中的 n n n個元素互不相等，則

    C[A[j]]

    的值即為元素

    A[j]

    在輸出序列中的最終位置；
  • 由于待排序列

    A

    中的元素可能相同，則在輸出序列

    B

    中放置好某元素

    A[j]

    後，需要将

    C[A[j]]

    減1，這樣一來，如果後續仍有元素等于

    A[j]

    ，則該元素将會被放置到序列

    B

    中元素

    A[j]

    的前一個位置。

3. 圖解

為使讀者更好地了解上述計數排序算法

counting_sort

，下圖描述了算法的執行過程，其中：

• 待排序列

  A[1..8]

  中的每個元素均是小于 k = 5 k=5 k=5的非負整數；
• 圖 ( a ) (a) (a)表示執行完第6行之後的待排序列

  A和

  輔助序列

  C

  ；
• 圖 ( b ) (b) (b)表示執行完第9行之後的輔助序列

  C

  ；
• 圖 ( c ) (c) (c)到 ( e ) (e) (e)分别表示第11至13行的

  for

  循環分别完成1、2、3次疊代後輸出序列

  B

  和輔助序列

  C

  的情況；
• 圖 ( f ) (f) (f)表示最終有序的輸出序列

  B

  。

4. 代碼實作

下面是計數排序的Python實作：

def count_sort(arr):
    """計數排序"""
    # 将輔助計數序列的元素全部初始化為0
    count = [0 for _ in range(256)]

    # 統計arr中每個元素的個數，且該個數值儲存在count的索引arr[j]處
    for j in range(len(arr)):
        count[arr[j]] += 1

    # 使得count[i]處儲存小于或等于i的元素個數
    for i in range(256):
        count[i] += count[i - 1]

    # 依次将arr中的元素放置到輸出序列的有序位置處
    output = [0 for _ in range(len(arr))]
    for j in range(len(arr) - 1, -1, -1):  # 確定計數排序是穩定的
        output[count[arr[j]] - 1] = arr[j]
        count[arr[j]] -= 1

    # 切片拷貝
    arr[:] = output[:]


if __name__ == '__main__':
    arr = [2, 5, 3, 0, 2, 3, 0, 3]
    count_sort(arr)
    print(arr)  # [0, 0, 2, 2, 3, 3, 3, 5]
           

5. 時間複雜度

關于計數排序的時間複雜度，通過分析計數排序

counting_sort

的僞代碼可以友善地得出，即：

• 第3至4行的

  for

  循環需要的時間為 Θ ( k ) \Theta(k) Θ(k)；
• 第5至6行的

  for

  循環需要的時間為 Θ ( n ) \Theta(n) Θ(n)；
• 第8至9行的

  for

  循環需要的時間為 Θ ( k ) \Theta(k) Θ(k)；
• 第11至13行的

  for

  循環需要的時間為 Θ ( n ) \Theta(n) Θ(n)。

綜上，計數排序總的時間複雜度為 Θ ( n + k ) \Theta(n+k) Θ(n+k)，而在實際中當 k = O ( n ) k=O(n) k=O(n)，即待排序列的元素大小和待排序列元素個數相當，則計數排序的最壞時間複雜度為 Θ ( n ) \Theta(n) Θ(n)。

二、基數排序

1. 簡介

上面我們說實際中當 k = O ( n ) k=O(n) k=O(n)時，計數排序的最壞時間複雜度為 Θ ( n ) \Theta(n) Θ(n)，但是當 k = Ω ( n ) k=\Omega(n) k=Ω(n)時，例如 k = n 2 k=n^2 k=n2，此時計數排序的時間複雜度為 Θ ( n 2 ) \Theta(n^2) Θ(n2)，此時下面即将介紹的基數排序可能更加高效。

基數排序的思想很簡單，以下圖為例，給定7個3位數，從低位到高位開始，對其進行三輪排序，每一輪僅考慮使用目前位的數值進行排序。

2. 代碼實作

對于基數排序的實作，可以使用上述計數排序來實作，因為每一輪排序中，每一位的數值都在0到9的範圍内，即 k = m a x ( [ 0 , ⋅ ⋅ ⋅ , 9 ] ) = 9 k=max([0,\cdot\cdot\cdot,9])=9 k=max([0,⋅⋅⋅,9])=9，此時計數排序可視為 Θ ( n + k ) ≈ Θ ( n ) \Theta(n+k)\approx{\Theta(n)} Θ(n+k)≈Θ(n)。

def counting_sort(arr, exp):
    """
    按照位對arr中的元素進行計數排序
    :param arr: 待排序列
    :param exp: 指定排序位數，用10的非負整數次幂表示
    :return: None
    """

    # 初始化計數用輔助序列
    count = [0 for _ in range(10)]

    # 對于arr中的每個元素，得到其某位的值digit，并将統計得到的相同digit數量儲存在count[digit]處
    for j in range(len(arr)):
        digit = (arr[j] // exp) % 10
        count[digit] += 1

    # 使得count[i]處儲存小于或等于i的元素個數
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 建立有序的輸出序列
    output = [0 for _ in range(len(arr))]
    for j in range(len(arr) - 1, -1, -1):  # 確定計數排序是穩定的
        digit = (arr[j] // exp) % 10
        output[count[digit] - 1] = arr[j]
        count[digit] -= 1

    # 切片拷貝
    arr[:] = output[:]


def radix_sort(arr):
    """
    基數排序
    """

    # 找到待排序列中的最大值
    max_num = max(arr)

    # 從低位到高位，對待排序列依次做計數排序，其中exp表示十進制基數，
    # 如：exp = 10^0表示個位，exp = 10^1表示十位，以此類推
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10


if __name__ == '__main__':
    arr = [329, 457, 657, 839, 436, 720, 355]
    radix_sort(arr)
    print(arr)  # [329, 355, 436, 457, 657, 720, 839]
           

3. 時間複雜度

假設給定 n n n個具有 d d d位的數值，且每一位最大可能為 k k k，如果對每一位進行排序的算法（上述是計數排序）最壞時間複雜度為 Θ ( n + k ) \Theta(n+k) Θ(n+k)，則基數排序的最壞時間複雜度為 Θ ( d ( n + k ) ) \Theta(d(n+k)) Θ(d(n+k))。

三、桶排序

1. 簡介

假定 n n n個待排序列的元素由某随機過程産生，且每個元素均勻且獨立分布于區間 [ 0 , m a x ( a r r ) ] [0, max(arr)] [0,max(arr)]，則桶排序的思想在于：

• 先将區間 [ 0 , m a x ( a r r ) ] [0, max(arr)] [0,max(arr)]分為 n n n個等間隔子區間（這些子區間又被稱為桶）；
• 然後将 n n n個待排元素分散到對應的桶中；
• 接着對每個桶中元素進行排序（例如使用插入排序）；
• 最後從左至右按順序将每一個桶中的元素取出合并即得有序序列。

2. 實作

下面是桶排序的Python實作：

def bucket_sort(arr):
    """桶排序"""
    # 确定桶的大小
    bucket_size = max(arr) / len(arr)
    # 初始化所有桶
    buckets = [[] for _ in range(len(arr))]
    # 依次将元素放入對應的桶中
    for i in range(len(arr)):
        j = int(arr[i] / bucket_size)  # 向下取整，得到元素應該被放進的桶的序号
        if j != len(arr):
            buckets[j].append(arr[i])
        else:
            buckets[len(arr) - 1].append(arr[i])

    # 對每一個桶中的元素使用插入排序
    for i in range(len(arr)):
        print(f'bucket[{i}] = {buckets[i]}')
        insertion_sort(buckets[i])

    # 将所有桶中元素順次拼接
    result = []
    for i in range(len(arr)):
        result = result + buckets[i]
    return result


def insertion_sort(bucket):
    """插入排序"""
    for i in range(1, len(bucket)):
        current = bucket[i]
        j = i - 1
        while j >= 0 and current < bucket[j]:  # 隻有同時滿足條件才進行元素右移
            bucket[j + 1] = bucket[j]
            j = j - 1
        bucket[j + 1] = current  # 将元素current插入正确的位置


if __name__ == '__main__':
    arr = [12, 34, 32, 65, 76, 43, 54]
    sorted_arr = bucket_sort(arr)
    print(sorted_arr)
           

3. 時間複雜度

首先給出結論：

桶排序的平均時間複雜度為 Θ ( n ) \Theta(n) Θ(n)。

下面給出證明：

上述桶排序的實作中，除了第18行調用插入排序外，總的最壞時間複雜度為 Θ ( n ) \Theta(n) Θ(n)，如果假定第

i

個桶

buckets[i]

中元素個數為 n i n_i ni​，又因為插入排序的最壞時間複雜度為 O ( n i 2 ) O(n_i^2) O(ni2​)，是以桶排序的時間複雜度可由以下表示：

T ( n ) = Θ ( n ) + ∑ i = 0 n − 1 O ( n i 2 ) T(n)={\Theta(n)}+\sum_{i=0}^{n-1}{O(n_i^2)} T(n)=Θ(n)+i=0∑n−1​O(ni2​)

考慮待排序列中的元素均由具有相同區間上下限且互相獨立的均勻分布産生，下面通過計算 T ( n ) T(n) T(n)的數學期望的方式來得出桶排序的平均時間複雜度。

首先，根據數學期望的線性性質有：

E [ T ( n ) ] = E [ Θ ( n ) + ∑ i = 0 n − 1 O ( n i 2 ) ] = Θ ( n ) + ∑ i = 0 n − 1 E [ O ( n i 2 ) ] = Θ ( n ) + ∑ i = 0 n − 1 O ( E [ n i 2 ] ) \begin{aligned} E[T(n)] &= E\left[{\Theta(n)}+\sum_{i=0}^{n-1}{O(n_i^2)}\right] \\ &= {\Theta(n)} +\sum_{i=0}^{n-1}E\left[{O(n_i^2)}\right]\\ &= {\Theta(n)} +\sum_{i=0}^{n-1}{O(E\left[n_i^2\right])} \end{aligned} E[T(n)]​=E[Θ(n)+i=0∑n−1​O(ni2​)]=Θ(n)+i=0∑n−1​E[O(ni2​)]=Θ(n)+i=0∑n−1​O(E[ni2​])​

然後由于對待排序列中的每一個元素，其都是等可能落入任意一個桶内，是以對于任意 i = 0 , 1 , ⋅ ⋅ ⋅ , n − 1 i=0,1,\cdot\cdot\cdot,n-1 i=0,1,⋅⋅⋅,n−1，有 E [ n i 2 ] E\left[n_i^2\right] E[ni2​]均相等。

進一步，可以證明 E [ n i 2 ] = 2 − 1 n E\left[n_i^2\right]=2-\frac{1}{n} E[ni2​]=2−n1​：

具體地，可以定義一個随機變量 X i j X_{ij} Xij​，即 X i j = 1 X_{ij}=1 Xij​=1表示元素

arr[j]

落入桶

buckets[i]

内， X i j = 0 X_{ij}=0 Xij​=0表示元素

arr[j]

不落入桶

buckets[i]

内，其中 i , j = 0 , 1 , ⋅ ⋅ ⋅ , n − 1 i,j=0,1,\cdot\cdot\cdot,n-1 i,j=0,1,⋅⋅⋅,n−1，是以：

n i = ∑ j = 0 n − 1 X i j n_i=\sum_{j=0}^{n-1}X_{ij} ni​=j=0∑n−1​Xij​

故：

E [ n i 2 ] = E [ ( ∑ j = 0 n − 1 X i j ) 2 ] = E [ ∑ j = 0 n − 1 X i j ∑ j = 0 n − 1 X i j ] = E [ ∑ j = 0 n − 1 X i j ∑ k = 0 n − 1 X i k ] = E [ ∑ j = 0 n − 1 ∑ k = 0 n − 1 X i k X i j ] = E [ ∑ j = 0 n − 1 X i j 2 + ∑ 0 ≤ j ≤ n − 1 ∑ 0 ≤ k ≤ n − 1 k ≠ j X i j X i k ] = ∑ j = 0 n − 1 E [ X i j 2 ] + ∑ 0 ≤ j ≤ n − 1 ∑ 0 ≤ k ≤ n − 1 k ≠ j E [ X i j X i k ] \begin{aligned} E\left[n_i^2\right] &= E\left[\left(\sum_{j=0}^{n-1}X_{ij}\right)^2\right] \\ & = E\left[\sum_{j=0}^{n-1}X_{ij}\sum_{j=0}^{n-1}X_{ij}\right] \\ & = E\left[\sum_{j=0}^{n-1}X_{ij}\sum_{k=0}^{n-1}X_{ik}\right] \\ & = E\left[\sum_{j=0}^{n-1}{\sum_{k=0}^{n-1}X_{ik}}X_{ij}\right] \\ & = E\left[\sum_{j=0}^{n-1}X_{ij}^2+\sum_{0\le{j}\le{n-1}}{\sum_{0\le{k}\le{n-1}}^{k\ne{}j}}X_{ij}X_{ik}\right] \\ & = \sum_{j=0}^{n-1}E\left[X_{ij}^2\right]+\sum_{0\le{j}\le{n-1}}{\sum_{0\le{k}\le{n-1}}^{k\ne{}j}}E\left[X_{ij}X_{ik}\right] \end{aligned} E[ni2​]​=E⎣⎡​(j=0∑n−1​Xij​)2⎦⎤​=E[j=0∑n−1​Xij​j=0∑n−1​Xij​]=E[j=0∑n−1​Xij​k=0∑n−1​Xik​]=E[j=0∑n−1​k=0∑n−1​Xik​Xij​]=E[j=0∑n−1​Xij2​+0≤j≤n−1∑​0≤k≤n−1∑k​=j​Xij​Xik​]=j=0∑n−1​E[Xij2​]+0≤j≤n−1∑​0≤k≤n−1∑k​=j​E[Xij​Xik​]​

由于 X i j = 1 X_{ij}=1 Xij​=1的機率為 1 n \frac{1}{n} n1​， X i j = 0 X_{ij}=0 Xij​=0的機率為 n − 1 n \frac{n-1}{n} nn−1​，是以：

E [ X i j 2 ] = 1 2 ⋅ 1 n + 0 2 ⋅ n − 1 n = 1 n \begin{aligned} E\left[X_{ij}^2\right] &= 1^2\cdot{\frac{1}{n}}+0^2\cdot{\frac{n-1}{n}} \\ &= {\frac{1}{n}} \end{aligned} E[Xij2​]​=12⋅n1​+02⋅nn−1​=n1​​

而當 k ≠ j k\ne{j} k​=j時，随機變量 X i j X_{ij} Xij​和 X i k X_{ik} Xik​互相獨立，是以：

E [ X i j X i k ] = E [ X i j ] E [ X i k ] = 1 n ⋅ 1 n = 1 n 2 \begin{aligned} E\left[X_{ij}X_{ik}\right] &= E\left[X_{ij}\right]E\left[X_{ik}\right] \\ &= {\frac{1}{n}}\cdot{{\frac{1}{n}}} \\ &= \frac{1}{n^2} \end{aligned} E[Xij​Xik​]​=E[Xij​]E[Xik​]=n1​⋅n1​=n21​​

是以：

E [ n i 2 ] = ∑ j = 0 n − 1 1 n + ∑ 0 ≤ j ≤ n − 1 ∑ 0 ≤ k ≤ n − 1 k ≠ j 1 n 2 = n ⋅ 1 n + n ( n − 1 ) ⋅ 1 n 2 = 1 + n − 1 n = 2 − 1 n \begin{aligned} E\left[n_i^2\right] &= \sum_{j=0}^{n-1}\frac{1}{n}+\sum_{0\le{j}\le{n-1}}{\sum_{0\le{k}\le{n-1}}^{k\ne{}j}}\frac{1}{n^2} \\ & = n\cdot{\frac{1}{n}}+n(n-1)\cdot{\frac{1}{n^2}} \\ & = 1+\frac{n-1}{n} \\ & = 2-\frac{1}{n} \end{aligned} E[ni2​]​=j=0∑n−1​n1​+0≤j≤n−1∑​0≤k≤n−1∑k​=j​n21​=n⋅n1​+n(n−1)⋅n21​=1+nn−1​=2−n1​​

至此，證畢。

使用上述結果帶入本節開頭的 E [ T ( n ) ] E[T(n)] E[T(n)]公式可得：

E [ T ( n ) ] = Θ ( n ) + n ⋅ O ( 2 − 1 n ) = Θ ( n ) E[T(n)]=\Theta(n)+n\cdot{O(2-\frac{1}{n})}=\Theta(n) E[T(n)]=Θ(n)+n⋅O(2−n1​)=Θ(n)