以下几种排序算法的时间复杂度为O(n),因为它们使用的是基于数字本身的排序。 (1) 桶排序! 基本思想:设计 M 个桶,根据元素本身进行分配。因为 M 个桶是按顺序排列的,所以分配元素之后元素也会按顺序排列。 待排序的数据范围不太大时可以考虑这样排序(比如1~1000可以考虑,而1~100000就必须用快速排序)。 下面假设每个数都位于区间[1, M]。 int cnt[M]; memset(cnt,0,sizeof(cnt)); for (int i=0; i<N; i++) cnt[a]++; // 从cnt[0]开始挨个列举就行了。例如 for (int i=0; i<M; i++) while ((cnt--)>0) cout<<i<<" "; |
(2) 计数排序 基本思想:对于序列中的每一元素 x,确定序列中小于 x 的元素的个数。下面假设每个数都位于区间[1, m]。 int a[N], b[N], cnt[M]; …… memset(cnt,0,sizeof(cnt)); for (int i=0;i<n;i++) cnt[a]++; for (int i=1;i<M;i++) cnt+=cnt[i-1]; for (int i=n-1;i>0;i--) { b[cnt[a]] = a; cnt[a]--; } // 输出结果 for (int i=0;i<n;i++) cout<<b<<' '; |
(3) 基数排序* 基本思想:对 n 个元素依次按 k,k-1,...1位上的数字进行桶排序。 int tmp[N], cnt[10]; int n; int maxbit(int *data, int n) { | | | | | | | | | | int p =10; for (int i = 0;i < n; i++) while (data >= p) p *= 10, d++; return d; } void radixsort(int *data, int n) | | | | | int d = maxbit(data,n); int i,j,k; int radix = 1; for (i = 1; i<= d;i++) | | | | | { for (j = 0;j < 10;j++) cnt[j] = 0; | | | | | for (j = 0;j < n; j++) { k = (data[j]/radix)%10; | | | | | cnt[k]++; } for (j = 1;j < 10;j++) cnt[j] = cnt[j-1] + cnt[j]; | | | | | | | | | | | | { k = (data[j]/radix)%10; cnt[k]--; tmp[cnt[k]] = data[j]; } for (j = 0;j < n;j++) data[j] = tmp[j]; radix = radix*10; | | | | | | | |
|