计数排序

主要是将值作为下标，然后计算有多少小于该值的数，然后再把相应的值放入到相应的位置，如果有相同的值则最先扫描到的放到可能的最后的位置。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include <cstdio> #include <cstdlib> #include <string> #include <queue> #include <algorithm> #include <map> #include <iomanip> #define INF 999999999 using namespace std; const int MAX = 10000; int len, arr[MAX]; int mark[MAX], temp[MAX]; void (int *arr, int len) { cout << "--------------------"; for(int i = 0; i < len; ++i) { cout << arr[i] << ' '; } cout << "------------------n"; } void calSort(int *arr, int len) { for(int i = 0; i < MAX; ++i) mark[i] = 0; for(int i = 0; i < len; ++i) mark[arr[i]] += 1; for(int i = 1; i < MAX; ++i) mark[i] += mark[i-1]; for(int i = 0; i < len; ++i) temp[--mark[arr[i]]] = arr[i]; for(int i = 0; i < len; ++i) arr[i] = temp[i]; } int main() { cin >> len; for(int i = 0; i < len; ++i) { cin >> arr[i]; } calSort(arr, len); output(arr, len); return 0; }