- 桶排序思想下的排序：计数排序 & 基数排序
- 桶排序思想下的排序都是不基于比较的排序
- 时间复杂度为 O(N)，额外空间负载度 O(M)
- 应用范围有限，需要样本的数据状况满足桶的划分
- 计数排序和基数排序
- 一般来讲，计数排序要求，样本是整数，且范围比较窄
- 一般来讲，基数排序要求，样本是10进制的正整数
一旦要求稍有升级，改写代价增加是显而易见的
2、过程模拟1、计数排序
比如给定一个数组 arr，数组中的所有数范围是0 ~ 200，那么设置一个辅助数组 help，下标范围0 ~ 201，遍历原始数组 arr，help[i] 记录 i 这个数出现的次数，然后再遍历一遍 help 数组，就能得到最终的排序结果；时间复杂度 O ( N ) O(N) O(N)。
2、基数排序
【约束】非负 且为 10进制整数，如果数据包含负数，先找到最小值 -x，然后所有数统一加上 x，排序，最后每个数再减去 x
【流程】
1）假设给定数组 [103, 13, 27, 25, 17, 9]，先遍历一遍找到最大值 103，不够 3 位的数高位补 0，原数组就变成了 [103, 013, 027, 025, 017, 009]，准备10个桶，每个桶对应于每个数字（0对应0，1对应1）；
2）先按照数组中数字的 个位 放入不同的桶中，103 放到 3 这个桶，013 放到 3 这个桶，027 放到 7 这个桶，…，先入先出，然后遍历这些桶，倒出数字，得到了数组 [103, 013, 025, 027, 017, 009] （根据个位排序）；
3）然后当前的这个数组的所有数字从左往右根据 十位 进桶，然后倒出来得到数组 [103， 009， 013， 017， 025， 027] ；
4）最后当前这个数组的所有数字从左到右根据 百位 进桶，然后倒出来得到数组 [009, 013, 017, 025, 027, 103]，已经有序了。
3、代码实现 C++版 计数排序//计数排序 #include基数排序#include using namespace std; void countSort(vector &arr) { if (arr.size() < 2) return ; int maxVal = INT_MIN; for (int i = 0; i < arr.size(); i++) { maxVal = max(maxVal, arr[i]); } vector bucket(maxVal + 1, 0); for (int i = 0; i < arr.size(); i++) { bucket[arr[i]]++; } int i = 0; for (int j = 0; j < bucket.size(); j++) { while (bucket[j]-- > 0) { arr[i++] = j; } } } void comparator(vector &arr) { sort(arr.begin(), arr.end()); } vector generateRandomArray(int maxSize, int maxVal) { vector arr(rand() % (maxSize + 1)); for (int i = 0; i < arr.size(); i++) { arr[i] = rand() % (maxVal + 1); } return arr; } vector copyArray(vector &arr) { vector res(arr.size()); for (int i = 0; i < arr.size(); i++) { res[i] = arr[i]; } return res; } bool isEqual(vector &arr1, vector &arr2) { if (arr1.size() != arr2.size()) return false; for (int i = 0; i < arr1.size(); i++) { if (arr1[i] != arr2[i]) return false; } return true; } void printArray(vector &arr) { for (int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } cout << endl; } int main() { srand(time(0)); int testTime = 500000; int maxSize = 100; int maxVal = 150; bool succeed = true; for (int i = 0; i < testTime; i++) { vector arr1 = generateRandomArray(maxSize, maxVal); vector arr2 = copyArray(arr1); countSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } cout << (succeed ? "Nice" : "Fucking fucked!") << endl; vector arr = generateRandomArray(maxSize, maxVal); printArray(arr); countSort(arr); printArray(arr); return 0; }
#include#include #include #include using namespace std; //x 的第d位的值 int getDigit(int x, int d) { return (x / ((int)(pow(10, d - 1)))) % 10; } //不使用桶也实现了出桶和入桶 void radixSort(vector &arr, int l, int r, int digit) { int radix = 10; int i = 0, j = 0; vector help(r - l + 1); for (int d = 1; d <= digit; d++) { vector count(radix); for (i = l; i <= r; i++) { j = getDigit(arr[i], d); count[j]++; } for (i = 1; i < radix; i++) { count[i] = count[i] + count[i - 1]; } for (i = r; i >= l; i--) { j = getDigit(arr[i], d); help[count[j] - 1] = arr[i]; count[j]--; } for (i = l, j = 0; i <= r; i++, j++) { arr[i] = help[j]; } } } //获取最大值的位数 int maxBits(vector &arr) { int maxVal = INT_MAX; for (int i = 0; i < arr.size(); i++) { maxVal = max(maxVal, arr[i]); } int res = 0; while (maxVal != 0) { res++; maxVal /= 10; } return res; } //基数排序 void radixSort(vector &arr) { if (arr.size() < 2) return ; radixSort(arr, 0, arr.size() - 1, maxBits(arr)); } void comparator(vector &arr) { sort(arr.begin(), arr.end()); } vector generateRandomArray(int maxSize, int maxVal) { vector arr(rand() % (maxSize + 1)); for (int i = 0; i < arr.size(); i++) { arr[i] = rand() % (maxVal + 1); } return arr; } vector copyArray(vector &arr) { vector res(arr.size()); for (int i = 0; i < arr.size(); i++) { res[i] = arr[i]; } return res; } bool isEqual(vector &arr1, vector &arr2) { if (arr1.size() != arr2.size()) return false; for (int i = 0; i < arr1.size(); i++) { if (arr1[i] != arr2[i]) return false; } return true; } void printArray(vector &arr) { for (int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } cout << endl; } int main() { srand(time(0)); int testTime = 500000; int maxSize = 100; int maxValue = 100000; bool succeed = true; for (int i = 0; i < testTime; i++) { vector arr1 = generateRandomArray(maxSize, maxValue); vector arr2 = copyArray(arr1); radixSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { cout << "Oops!" << endl; succeed = false; printArray(arr1); printArray(arr2); break; } } cout << (succeed ? "Nice" : "Fucking fucked!") << endl; vector arr = generateRandomArray(maxSize, maxValue); printArray(arr); radixSort(arr); printArray(arr); return 0; }
其中 radixSort(vector
以个位为例，从右往左遍历 arr 数组，根据个位的值 val 在 count 数组中 count[val]，决定当前数应该放在 help数组的哪个位置。
完整流程模拟
比如数组arr： [101, 001, 022, 031, 040]，
针对个位，得到count数组: [1 3 1 0 0 0 0 0 0 0] —— 【count[i] 表示当前位为 i 的数的个数】
然后 count 数组变成 count' 数组：[1 4 5 5 5 5 5 5 5 5] —— 【count'[i] 表示所有数字中个位 <= i 的数的个数】
提前准备好辅助数组 help，然后从右往左遍历 arr 数组；
-
遍历到 040 的时候，count'[0] = 1，也就是个位 <=0 的数只有 1个，那么就是这个数本身，所以 help[0] = 040，然后将 count'[0]--，count'[0] 就变成 0
-
接着遍历到 031，count'[1] = 4，即是说个位 <=1 的数共有 4 个，那么就知道 <=1 的整体范围是下标 0~3，又因为是从右往左遍历，所以 031 就应该占据 help[3] 的位置，所以 help[3] = 031， 将 count'[1]--, 使用过一次之后就要减去1，count'[1] = 3，此时 count' 数组就变成了 [0 3 5 5 5 5 5 5 5 5]
-
接着遍历到 022，个位 <=2 的数的个数为 5，占据 0~4 范围，而是从右往左遍历的，所以 help[4] = 022, 然后将 count'[2]--，count' 数组变成 [0 3 4 5 5 5 5 5 5 5]
-
接着遍历到 001，个位 <=1 的数个数为 3, 占据 0 ~ 2 范围，且是从右往左遍历的，所以 help[2] = 001，然后将 count'[1]--，count'数组变成 [0 2 4 5 5 5 5 5 5 5]
-
最后遍历到 101，个位 <=1 的数个数为 2，占据 0~1范围，因为从右往左遍历，所以 help[1] = 101
至此，根据个位进行的排序结果：help 数组 [040 101 001 031 022]，将这个数组倒到 arr 数组中
注意：count' 中的值只关心当前数出现的位置，所以当某个数被判断后，只需要减去当前这个数的计数，而不用管其他位置的数
优点：节省了桶的空间，不要桶也优雅地实现了基数排序
实际的时间复杂度是 O ( N ∗ l o g ( 10 , m a x ) ) O(N * log(10, max)) O(N∗log(10,max))，当 max不是特别大的时候，就是 O ( N ) O(N) O(N)； 但是当 max 比较大的时候，复杂度就得写成 O ( N ∗ l o g ( 10 , m a x ) ) O(N * log(10, max)) O(N∗log(10,max))
Java 版 计数排序public class CountSort {
// only for 0~200 value
public static void countSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
int i = 0;
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
}
// for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 150;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
countSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
countSort(arr);
printArray(arr);
}
}
基数排序
public class RadixSort {
// only for no-negative value
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
// arr[L..R]排序, 最大值的十进制位数digit
public static void radixSort(int[] arr, int L, int R, int digit) {
final int radix = 10;
int i = 0, j = 0;
// 有多少个数准备多少个辅助空间
int[] help = new int[R - L + 1];
for (int d = 1; d <= digit; d++) { // 有多少位就进出几次
//无桶的优化版本，优雅实现了出桶入桶
// 10个空间
// count[0] 当前位(d位)是0的数字有多少个
// count[1] 当前位(d位)是(0和1)的数字有多少个
// count[2] 当前位(d位)是(0、1和2)的数字有多少个
// count[i] 当前位(d位)是(0~i)的数字有多少个
int[] count = new int[radix]; // count[0..9]
for (i = L; i <= R; i++) {
// 103 1 3
// 209 1 9
j = getDigit(arr[i], d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1]; //count数组变成前缀和数组，这个数组的含义是count[i]表示所有数字当前位 <= i 的数的个数
}
for (i = R; i >= L; i--) { //从右往左遍历原数组arr，确定当前数字应该在help的什么位置 （填数字的时候是从右往左填的）
j = getDigit(arr[i], d); //确定当前位的值
help[count[j] - 1] = arr[i];
count[j]--;
}
for (i = L, j = 0; i <= R; i++, j++) {
arr[i] = help[j];
}
}
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
// for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100000;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
radixSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
radixSort(arr);
printArray(arr);
}
}
