基數排序是在某種情況下比快速排序還快的排序.當然了,計數排序(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] << ' ';}新聞熱點
疑難解答
