以 O(n) 复杂度实现少于 100 个数字的排序的 C++ 程序
为了在线性时间内对一些小数进行排序,我们可以使用计数排序技术。
计数排序是一种稳定的排序技术,用于根据小数的键对对象进行排序。它计算键值相同的键的数量。当不同键之间的差异不大时,这种排序技术是有效的,否则会增加空间复杂度。
计数排序技术的复杂性
时间复杂度:O(n+r)
空间复杂度:O(n+r)
Input − A list of unsorted data: 2 5 6 2 3 10 3 6 7 8Output − Array after Sorting: 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 //将计数数组中的所有元素设置为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] //找到累积频率 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
示例代码
#includeusing 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 << "输入数组的大小: "; cin >> num; cout << "输入 " << num << " elements to be sorted:" << endl; for (i = 0; i < num; i++) cin >> array[i]; cout << "\nThe array of elements before sorting : " < 输出结果 输入数组的大小: 8 输入 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