計數排序（Counting Sort）是一種非比較性的排序演算法，適用於元素的範圍較小的情況。下面是計數排序的步驟：
建立一個計數陣列（Count array），用來記錄每個元素在原始陣列中出現的次數。計數陣列的大小為範圍內的最大值加一。
遍歷原始陣列，將每個元素的出現次數記錄在計數陣列中相應的位置。
將計數陣列進行累加，每個位置的值表示小於等於該位置的元素個數。
建立一個與原始陣列大小相同的輔助陣列，用於存儲排序後的結果。
遍歷原始陣列，根據計數陣列中的值將元素放入輔助陣列中的適當位置。
將排序後的結果複製回原始陣列。
以下是計數排序的 C 語言實現：
c
Copy code
#include <stdio.h>
void countingSort(int iArray[], int n) {
// 找出最大值
int max = iArray[0];
for (int i = 1; i < n; ++i) {
if (iArray[i] > max) {
max = iArray[i];
}
}
// 建立計數陣列
int count[max + 1];
for (int i = 0; i <= max; ++i) {
count[i] = 0;
}
// 統計元素出現次數
for (int i = 0; i < n; ++i) {
count[iArray[i]]++;
}
// 將計數陣列轉換為累加形式
for (int i = 1; i <= max; ++i) {
count[i] += count[i - 1];
}
// 建立輔助陣列，用於存儲排序後的結果
int output[n];
// 將元素放入輔助陣列中的適當位置
for (int i = n - 1; i >= 0; --i) {
output[count[iArray[i]] - 1] = iArray[i];
count[iArray[i]]--;
}
// 將排序後的結果複製回原始陣列
for (int i = 0; i < n; ++i) {
iArray[i] = output[i];
}
}
int main() {
int iArray[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(iArray) / sizeof(iArray[0]);
countingSort(iArray, n);
printf("排序後的結果：");
for (int i = 0; i < n; ++i) {
printf("%d ", iArray[i]);
}
printf("\n");
return 0;
}
這段程式碼可以將數組 iArray 使用計數排序方法排序。
阿摩線上測驗
登入
