以 O(n) 复杂度实现少于 100 个数字的排序的 C++ 程序

  • Z时代
  • 2024-01-10
  • 分类：综合

为了在线性时间内对一些小数进行排序，我们可以使用计数排序技术。

计数排序是一种稳定的排序技术，用于根据小数的键对对象进行排序。它计算键值相同的键的数量。当不同键之间的差异不大时，这种排序技术是有效的，否则会增加空间复杂度。

计数排序技术的复杂性

  • 时间复杂度：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

示例代码 

#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 << "输入数组的大小： ";
   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 : " <<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;
}
输出结果
输入数组的大小： 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

以上是 以 O(n) 复杂度实现少于 100 个数字的排序的 C++ 程序 的全部内容， 来源链接： utcz.com/z/331828.html

回到顶部