计数排序

计数排序假设n个输入元素中的每一个都是介于0到k之间的整数。其基本思想就是对每个输入元素x，确定小于x的元素个数。有了这一信息，就可以把x直接放到它在最终输出数组中的位置上。

 1 #include<iostream>
 2  void countsort(int *A,int *B,int n,int k)
 3  {
 4      //输入检查
 5 
 6 
 7      int *C = new int[k];//记录小于输入x的个数
 8      for (int i = 0; i < k;++i)
 9      {
10          C[i] = 0;
11      }
12      for (int i = 0; i < n;++i)
13      {
14          C[A[i]] = C[A[i]] + 1;
15      }
16 
17      for (int i = 1; i < k;++i)
18      {
19          C[i] = C[i - 1] + C[i];
20      }
21 
22      for (int i = n - 1; i >= 0;--i)
23      {
24          B[C[A[i]]-1] = A[i];
25          --C[A[i]];
26      }
27      delete[] C;
28  }
29 
30  int main()
31  {
32      int a[] = { 8, 4, 5, 6, 7 };
33      int *B = new int[5];
34      memset(B, 0, sizeof(int) * 5);
35      countsort(a, B, 5, 9);
36      for (int i = 0; i < 5;++i)
37      {
38          std::cout << B[i] << ' ';
39      }
40 
41      delete B;
42  }

相关推荐