計數排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 計數排序演算法
  2. 計數排序例項
  3. 計數排序演算法的實現
  4. 計數排序演算法的複雜度
計數排序

計數排序是一種非比較排序演算法。它通過計算每個唯一元素的出現次數對陣列進行排序。它對唯一元素的計數進行部分雜湊處理,然後執行計算以找到最終排序陣列中每個元素的索引。它是一個相當快的演算法,但不適合大型資料集。它作為基數排序中的一個子程式使用。

計數排序演算法

假設我們有一個無序陣列 A[],包含 n 個元素。

  • 求出陣列內的最大元素 max 和最小元素 min
  • 初始化一個長度為 max-min+1 的陣列 count,所有元素都設定為 0
  • 初始化一個陣列 output,大小與輸入陣列 A 相同。
  • count 陣列中所有元素的數量減去 min,並將其差值作為索引。
  • 累計 count 陣列內元素的總和。現在,count 陣列擁有排序陣列中每個元素的位置。
  • 從尾部開始,從 A 中抽取元素,並進行以下操作。
  • 計算元素索引為 count[A[i]-min]-1,並將 A[i] 儲存在 output 中。
  • count[A[i]-min] 減少 1
  • output 元素儲存回原陣列 A 中。

計數排序例項

假設我們有陣列。(6, 3, 2, 7, 4, 5, 4, 2). 我們將使用計數排序演算法對其進行排序。

  • maxm=7
  • minm=2
  • range=6
  • countoutput 初始化為 0。
索引 0 1 2 3 4 5
0 0 0 0 0 0
  • count 陣列在計算了所有元素的數量後。
索引 0 1 2 3 4 5
2 1 2 1 1 1
  • 累積元素之和後的 count 陣列。
索引 0 1 2 3 4 5
2 3 5 6 7 8
  • 第一次迭代:A[7]=2
count 1 3 5 6 7 8
output 0 2 0 0 0 0 0 0
  • 第二次迭代:A[6]=4
count 1 3 4 6 7 8
output 0 2 0 0 4 0 0 0
  • 第三次迭代:A[5]=5
count 1 3 4 5 7 8
output 0 2 0 0 4 5 0 0
  • 第四次迭代:A[4]=4
count 1 3 3 5 7 8
output 0 2 0 4 4 5 0 0
  • 第五次迭代:A[3]=7
count 1 3 3 5 7 7
output 0 2 0 4 4 5 0 7
  • 第六次迭代:A[2]=2
count 0 3 3 5 7 7
output 2 2 0 4 4 5 0 7
  • 第七次迭代:A[1]=3
count 0 2 3 5 7 7
output 2 2 3 4 4 5 0 7
  • 第八次迭代:A[0]=6
count 0 2 3 5 6 7
output 2 2 3 4 4 5 6 7

最後,我們把 output 陣列儲存在 A 裡面,得到排序陣列-2,2,3,4,4,5,6,7

計數排序演算法的實現

#include<iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }
    return max;
}

int minm(int arr[], int n) {
    int min = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
    }
    return min;
}

void countingSort(int arr[], int n) {
    int min = minm(arr, n);
    int max = maxm(arr, n);
    int range = max - min + 1;
    int count[range]={};
    int output[n];
    for (int i = 0; i < n; i++)
        count[arr[i] - min]++;

    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {

    int n = 7;
    int arr[7] = {3, 5, 1, 1, 4, 2, 1};
    cout << "Input arr: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    countingSort(arr, n); // Sort elements in ascending order
    cout << "Output arr: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

此實現也適用於負數。

計數排序演算法的複雜度

時間複雜度

  • 平均情況

計數排序對所有 n 項進行兩次迭代,對計數陣列進行一次迭代。因此,它的時間複雜度為 O(n+b),其中 b 是輸入的範圍。由於 b 通常較小,所以計數排序的時間複雜度可以說是 [Big Theta]:O(n)

  • 最壞情況

最壞情況下的時間複雜度為 [Big O]:O(n)

  • 最佳情況

最佳情況下的時間複雜度是 [Big Omega]:O(n)。它與最壞情況下的時間複雜度相同。

空間複雜度

計數排序演算法的空間複雜度為 O(n+b),其中 b 是輸入的範圍。它來自於 count&output 陣列。有時 b 可以比 n 大,但如果 b 小,時間複雜度可以說是 O(n)

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Sort Algorithm