資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 程式實現計數排序
計數排序是一種穩定的排序技術，它用於根據小數值型鍵對物件排序。它對鍵值相同的鍵的數量進行計數。當不同鍵之間的差異不是很大的時候，這種排序技術很有效；否則，它會導致空間複雜度增加。
計數排序技術的時間複雜度
時間複雜度：O(n+r)
空間複雜度：O(n+r)
輸入 - 一系列未排序的資料：2 5 6 2 3 10 3 6 7 8
輸出 - 排序後的陣列：2 2 3 3 5 6 6 7 8 10
演算法
countingSort(array, size)
輸入：一個數據陣列和陣列中的總數
輸出：已排序的陣列
Begin max = get maximum element from array. define count array of size [max+1] for i := 0 to max do count[i] = 0 //set all elements in the count array to 0 done for i := 1 to size do increase count of each number which have found in the array done for i := 1 to max do count[i] = count[i] + count[i+1] //find cumulative frequency done for i := size to 1 decrease by 1 do store the number in the output array decrease count[i] done return the output array End
示例程式碼
#include<iostream>
#include<algorithm>
using namespace std;
void display(int *array, int size) {
for(int i = 1; i<=size; i++)
cout << array[i] << " ";
cout << endl;
}
int getMax(int array[], int size) {
int max = array[1];
for(int i = 2; i<=size; i++) {
if(array[i] > max)
max = array[i];
}
return max; //the max element from the array
}
void countSort(int *array, int size) {
int output[size+1];
int max = getMax(array, size);
int count[max+1]; //create count array (max+1 number of elements)
for(int i = 0; i<=max; i++)
count[i] = 0; //initialize count array to all zero
for(int i = 1; i <=size; i++)
count[array[i]]++; //increase number count in count array.
for(int i = 1; i<=max; i++)
count[i] += count[i-1]; //find cumulative frequency
for(int i = size; i>=1; i--) {
output[count[array[i]]] = array[i];
count[array[i]] -= 1; //decrease count for same numbers
}
for(int i = 1; i<=size; i++) {
array[i] = output[i]; //store output array to main array
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n+1]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 1; i<=n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
countSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}輸出
Enter the number of elements: 10 Enter elements: 2 5 6 2 3 10 3 6 7 8 Array before Sorting: 2 5 6 2 3 10 3 6 7 8 Array after Sorting: 2 2 3 3 5 6 6 7 8 10
更新日期： 30-Jul-2019
4K+ 瀏覽
廣告