如何使用C++中的計數排序演算法

如何使用C 中的計數排序演算法

計數排序演算法是一種比較簡單且高效的排序演算法，適用於對整數序列進行排序的場景。它的基本思想是確定每個元素前面有多少個元素比它小，從而確定它在有序數組中的位置。

計數排序演算法的步驟如下：

1. 找出待排序數組中的最大值，以決定計數數組的長度。
2. 建立一個長度為最大值加一的計數數組，並初始化為0。
3. 遍歷待排序數組，統計每個元素的出現次數，並將統計結果儲存到計數數組。
4. 對計數數組進行變形，使得每個位置的值等於它前面位置值總和。
5. 建立一個與待排序數組等長的臨時數組，用於保存排序結果。
6. 從後向前遍歷待排序數組，根據計數數組確定每個元素在排序結果中的位置，並將元素儲存到臨時數組中。
7. 將臨時數組的結果複製回待排序數組，完成排序。

下面是一個使用C 語言實現的計數排序演算法的範例程式碼：

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    vector<int> count(max_val + 1, 0);

    for (int i = 0; i < arr.size(); i++) {
        count[arr[i]]++;
    }

    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    vector<int> temp(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        temp[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < arr.size(); i++) {
        arr[i] = temp[i];
    }
}

int main() {
    vector<int> arr = {5, 1, 4, 3, 2};
    countingSort(arr);

    cout << "排序后的数组：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

以上程式碼中，我們使用了一個輔助的計數數組來統計每個元素的出現次數，然後透過變形計算每個元素在排序結果中的位置。最後，我們將排序結果複製回原數組。

透過上述範例程式碼，我們可以看到計數排序演算法的實作過程，它的時間複雜度為O(n k)，其中n為待排序序列的長度，k為最大元素值與最小元素值之差加一。

總結起來，計數排序演算法是一種簡單但高效的排序演算法，適用於對整數序列進行排序的場景。透過使用適當的資料結構和演算法，我們可以更好地完成排序任務。

以上是如何使用C++中的計數排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！