数据结构
网络
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+ 浏览
广告