实现计数排序的C ++程序
计数排序是一种稳定的排序技术，用于根据较小的键对对象进行排序。它计算键值相同的键的数量。当不同键之间的差异不太大时，此排序技术非常有效，否则会增加空间复杂度。
计数排序技术的复杂性
时间复杂度：O（n+r）
空间复杂度：O（n+r）
输入-未排序数据列表：25623103678
输出-排序后的数组：22335667810
算法
countSort(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