计数排序是一种稳定的排序技术,用于根据较小的键对对象进行排序。它计算键值相同的键的数量。当不同键之间的差异不太大时,此排序技术非常有效,否则会增加空间复杂度。
时间复杂度:O(n + r)
空间复杂度:O(n + r)
Input: A list of unsorted data: 2 5 6 2 3 10 3 6 7 8 Output: 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
counting sort(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 << "输入元素:" << 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 输入元素: 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