计数and基数排序

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<memory>//the hearder file of shared_ptr
 4 #include <vector>
 5 #include <list>
 6 #include <map>
 7 #include <string>
 8 //#include <cstring>
 9 #include <set>
10 
11 using namespace std;
12 
13 void cnt_sort(int *B, int *A, int n,int k) {//k为计数范围
14     unique_ptr<int[]> C(new int[k]);
15 
16     for (int i = 0;i < k;i++)C[i] = 0;
17     for (int i = 0;i < n;i++)C[A[i]]++;
18 
19     for (int i = 1;i < k;i++)C[i] += C[i - 1];
20 
21     for (int i = n - 1;i >= 0;i--)
22         B[--C[A[i]]] = A[i];
23         
24 }
25 
26 void radix_sort(int *A, int n) {//n为待排序数组大小
27 
28     int maxval = 0;//假设数组全为正数
29     for (int i = 0;i < n;i++)if (maxval < A[i])maxval = A[i];
30     int position = 1;
31     int *tmp = new int[n];
32 
33     while (maxval) {
34         vector<int> count(n, 0);
35         for (int i = 0;i < n;i++)count[A[i] / position % 10]++;
36         for (int i = 1;i < n;i++)count[i] += count[i - 1];
37 
38         for (int i = n;i > 0;i--)tmp[--count[A[i - 1] / position % 10]] = A[i - 1];//反向遍历保证排序的稳定
39         memcpy(A, tmp, sizeof(int)*n);
40         
41         position *= 10;
42         maxval /= 10;
43     }
44 }