计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。[1-2] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 const int maxn = 1000;
 5 const int k = 1000;
 6 vector<int> a(maxn);
 7 vector<int> c(maxn);
 8 vector<int> rand1(maxn);
 9 int main()
10 {
11     int n;
12     cin >> n;
13     for (int i = 0; i < n; i++)
14     {
15         cin >> a[i];
16         ++c[a[i]];
17     }
18     for (int i = 1; i < k; i++)
19     {
20         c[i] += c[i - 1];
21     }
22     for (int i = n - 1; i >= 0; --i)
23     {
24         rand1[--c[a[i]]] = a[i];
25     }
26     for (int i = 0; i < n; i++)
27     {
28         cout << rand1[i] << " ";
29     }
30     cout << endl;
31     system("pause");
32     return 0;
33 }

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 void countingsort(vector<int> vet, int k)
 5 {
 6     int len = vet.size();
 7     vector<int> b(len,0);
 8     vector<int> c(k+1,0);
 9     for (int i = 0; i < len; i++)
10         c[vet[i]]++;
11     for (int i = 1; i < k+1; i++)
12     {
13         c[i] = c[i] + c[i - 1];
14     }
15     for (int i = len - 1; i >= 0; i--)
16     {
17         b[--c[vet[i]]] = vet[i];
18     }
19     for (int i = 0; i < len; i++)
20     {
21         cout << b[i] << " ";
22     }
23 }
24 int main()
25 {
26     int n;
27     cin >> n;
28     vector<int> vet(n);
29     for (int i = 0; i < n; i++)
30     {
31         cin >> vet[i];
32     }
33     int max1 = INT_MIN;
34     for (int i = 0; i < n; i++)
35     {
36         if (vet[i]>max1)
37             max1 = vet[i];
38     }
39     countingsort(vet, max1);
40     system("pause");
41     return 0;
42 }