基数排序是在某种情况下比快速排序还快的排序.当然了,计数排序(Counting Sort)也有可能比快速排序快. 计数排序非常容易理解,时间复杂度是O(MAX(a[i])), 如果数据范围很小的话,计数排序有巨大优势. 而基数排序,则更进一步,对每一位进行计数排序. 这样时间复杂度降为O(N*log(MAX(a[i])) 以下代码实现了从小到大cntSort()和从大到小cntSort2().实际上也可以倒置得到从大到小,依然是O(N),代码比较迷的地方就是output数组,记住循环顺序,这个比较巧妙,具体参见 http://www.geeksforgeeks.org/radix-sort/
#include <bits/stdc++.h>using namespace std;int idx(int x, int exp){ return (x / exp) % 10;}void cntSort(int *a, int n, int exp){ int cnt[10] = {0}; int output[n]; for (int i = 0; i < n; i++) cnt[idx(a[i], exp)]++; for (int i = 1; i < 10; i++) cnt[i] += cnt[i - 1]; for (int i = n - 1; i >= 0; i--) { output[cnt[idx(a[i], exp)] - 1] = a[i]; cnt[idx(a[i], exp)]--; } for (int i = 0; i < n; i++) a[i] = output[i];}void cntSort2(int *a, int n, int exp){ int cnt[10] = {0}; int output[n]; for (int i = 0; i < n; i++) cnt[idx(a[i], exp)]++; for (int i = 8; i >= 0; i--) cnt[i] += cnt[i + 1]; for (int i = 0; i < n; i++) { output[cnt[idx(a[i], exp)] - 1] = a[i]; cnt[idx(a[i], exp)]--; } for (int i = 0; i < n; i++) a[i] = output[i];}int main(){ //freopen("in", "r", stdin); int n; scanf("%d", &n); int a[n]; int mx = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); mx = max(a[i], mx); } for (int exp = 1; mx / exp > 0; exp *= 10) cntSort(a, n, exp); for (int i = 0; i < n; i++) cout << a[i] << ' '; cout << endl; for (int exp = 1; mx / exp > 0; exp *= 10) cntSort2(a, n, exp); for (int i = 0; i < n; i++) cout << a[i] << ' ';}新闻热点
疑难解答
