数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序实现对小于100个数进行O(n)复杂度的排序
为了在线性时间内对一些小数字进行排序，我们可以使用计数排序技术。
计数排序是一种稳定的排序技术，用于根据作为小数字的键对对象进行排序。它计算键值相同的键的数量。当不同键之间的差异不大时，这种排序技术效率很高，否则它可能会增加空间复杂度。
计数排序技术的复杂度
时间复杂度：O(n + r)
空间复杂度：O(n + r)
Input − A list of unsorted data: 2 5 6 2 3 10 3 6 7 8 Output − Array after Sorting: 2 2 3 3 5 6 6 7 8 10
算法
countingSort(数组, 大小)
输入 - 数据数组，以及数组中的总数
输出 - 排序后的数组
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>
using namespace std;
void counting_sort(int array[], int n) {
int i, j;
int count[n];
for (i = 0; i < n; i++)
count[i] = 0;
for (i = 0; i < n; i++)
(count[array[i]])++;
for (i = 0, j = 0; i < n; i++)
for (; count[i] > 0; (count[i])--)
array[j++] = i;
}
int main() {
int array[100], i, num;
cout << "Enter the size of array : ";
cin >> num;
cout << "Enter the " << num << " elements to be sorted:" << endl;
for (i = 0; i < num; i++)
cin >> array[i];
cout << "\nThe array of elements before sorting : " <<endl;
for (i = 0; i < num; i++)
cout << array[i] << " ";
cout << "\nThe array of elements after sorting : " << endl;
counting_sort(array, num);
for (i = 0; i < num; i++)
cout << array[i] << " ";
return 0;
}输出
Enter the size of array : 8 Enter the 8 elements to be sorted: 54 89 23 20 18 88 65 31 The array of elements before sorting : 54 89 23 20 18 88 65 31 The array of elements after sorting : 54 89 23 20 18 88 65 31
更新于: 2019年7月30日
259 次浏览
广告