开篇介绍
大家好，我是 Java 最全面试题库 的提裤姐，明天这篇是数据结构与算法的第五篇，次要介绍 调配排序；在后续，会沿着第一篇开篇的常识线路始终总结上来，做到日更！如果我能做到百日百更，心愿你也能够跟着百日百刷，一百天养成一个好习惯。
调配排序
后面所探讨的排序算法均是基于关键字之间的比拟来实现的，而实践上已证实：
对于这样的排序，无论用何办法都至多要进行 [lgn] 次关键字的比拟。由 Stirling 公式可知 lgn≈nlgn-1.44n+0(lgn)，所以基于关键字比拟的排序工夫下界是 O(nlgn)。然而，若不通过比拟关键字来排序，则可能冲破此下界。调配排序正是如此，排序过程毋庸比拟关键字，而是通过“调配”和“收集”过程来实现排序，它们的工夫复杂度可达到线性阶：O(n)
调配排序包含 桶排序 和基数排序
桶排序
桶排序（箱排序 (Bucket sort)），工作的原理是将数组分到无限数量的桶子里。每个桶子再个别排序（有可能再应用别的排序算法或是以递归形式持续应用桶排序进行排序。
算法步骤：
假如有一组长度为 N 的待排关键字序列 K[1....n]。
1、首先将这个序列划分成 M 个的子区间(桶)。
2、而后基于某种映射函数，将待排序列的关键字 k 映射到第 i 个桶中(即桶数组 B 的下标 i)，那么该关键字 k 就作为 B[i] 中的元素 (每个桶B[i] 都是一组大小为 N/M 的序列)。
3、对每个桶 B[i] 中的所有元素进行比拟排序 (能够应用快排)。
4、而后顺次枚举输入B[0]....B[M] 中的全部内容即是一个有序序列
个性：
- 工夫复杂度：
O(n+k) - 空间复杂度：
O(n+k) - 稳定性：
稳固
代码实现：
public class BucketSort {private static final InsertSort insertSort = new InsertSort();
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不扭转参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {if (arr.length == 0) {return arr;}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {if (value < minValue) {minValue = value;} else if (value > maxValue) {maxValue = value;}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函数将数据调配到各个桶中
for (int i = 0; i < arr.length; i++) {int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {if (bucket.length <= 0) {continue;}
// 对每个桶进行排序，这里应用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {arr[arrIndex++] = value;
}
}
return arr;
}
/**
* 主动扩容，并保留数据
*
* @param arr
* @param value
*/
private int[] arrAppend(int[] arr, int value) {arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}基数排序
基数排序 (Radix Sort) 是桶排序的扩大，它的根本思维是：
将整数按位数切割成不同的数字，而后按每个位数别离比拟。
具体做法：将所有待比拟数值对立为同样的数位长度，数位较短的数后面补零。而后，从最低位开始，顺次进行一次排序。这样从最低位排序始终到最高位排序实现当前, 数列就变成一个有序序列。
算法步骤
1、将所有待比拟数值（正整数）对立为同样的数位长度，数位较短的数后面补零。
2、从最低位开始，顺次进行一次排序。
3、这样从最低位排序始终到最高位排序实现当前, 数列就变成一个有序序列。
个性：
- 工夫复杂度：
O(n*k) - 空间复杂度：
O(n+k) - 稳定性：
稳固
代码实现：
public class RadixSort {public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不扭转参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
/**
* 获取最高位数
*/
private int getMaxDigit(int[] arr) {int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private int getMaxValue(int[] arr) {int maxValue = arr[0];
for (int value : arr) {if (maxValue < value) {maxValue = value;}
}
return maxValue;
}
protected int getNumLenght(long num) {if (num == 0) {return 1;}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {lenght++;}
return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {// 思考正数的状况，这里扩大一倍队列数，其中 [0-9]对应正数，[10-19]对应负数 (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {for (int value : bucket) {arr[pos++] = value;
}
}
}
return arr;
}
/**
* 主动扩容，并保留数据
*
* @param arr
* @param value
*/
private int[] arrayAppend(int[] arr, int value) {arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}