堆排序的时间复杂度也是O(nlogn),这个也是有一定的概率在面试中被考察到，其实如果真实在面试中遇到后，可以在实现上不用自己去维护一个堆，而是用Java中的PriorityQueue来实现，可以将无序数据集合放入到PriorityQueue中，然后再依次取出堆顶数据，取出堆顶数据时要从堆中移除取出的这个元素，这样每次取出的就都是现有数据中最小的元素了。
计数排序
计数排序是一种线性时间复杂度的排序算法，它主要的逻辑时将数据转化为键存储在额外的数组空间里。计数排序有一定的局限性，它要求输入的数据，必须是有确定范围的整数序列。
主要步骤：
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
动图演示
代码模板
/**
* 计数排序
* @param array
*/
public static void countSort(int[] array){
int bucketLen = getMaxValue(array) + 1;
int[] bucket = new int[bucketLen];
// 统计每个值出现的次数
for (int value : array) {
bucket[value]++;
}
// 反向填充数组
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
array[sortedIndex++] = j;
bucket[j]--;
}
}
}
/**
* 获取最大值
* @param arr
* @return
*/
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
桶排序
桶排序算是计数排序的一个加强版，它利用特定函数的映射关系，将属于一定范围内的数据，放到一个桶里，然后对每个桶中的数据进行排序，最后再将排序好的数据拼接起来。
主要步骤：
设置一个合适长度的数组作为空桶；
遍历数据，将数据都放到指定的桶中，分布的越均匀越好；
对每个非空的桶里的数据进行排序；
将每个桶中排序好的数据拼接在一起。
动图演示
代码模板
/**
* 桶排序
* @param arr
* @param bucketSize
* @return
*/
private static int[] bucketSort(int[] arr, int bucketSize){
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] = appendBucket(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了插入排序
InsertSort.insertSort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
/**
* 扩容，并追加数据
*
* @param array
* @param value
*/
private static int[] appendBucket(int[] array, int value) {
array = Arrays.copyOf(array, array.length + 1);
array[array.length - 1] = value;
return array;
}
基数排序
基数排序是一种非比较型排序，主要逻辑时将整数按位拆分成不同的数字，然后再按照位数排序，先按低位排序，进行收集，再按高位排序，再进行收集，直到最高位。
主要步骤：
获取原始数据中的最大值以及最高位；
在原始数组中，从最低位开始取每个位组成基数数组；
对基数数组进行计数排序（利用计数排序适用于小范围数的特点）；
动图演示
代码模板
/**
* 基数排序
* @param array
*/
public static void radixSort(int[] array){
// 获取最高位
int maxDigit = getMaxDigit(array);
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 < array.length; j++) {
int bucket = ((array[j] % mod) / dev) + mod;
counter[bucket] = appendBucket(counter[bucket], array[j]);
}
// 反向填充数组
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
array[pos++] = value;
}
}
}
}
/**
* 获取最高位数
*/
private static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLength(maxValue);
}
/**
* 获取最大值
* @param arr
* @return
*/
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
/**
* 获取整数的位数
* @param num
* @return
*/
protected static int getNumLength(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
/**
* 扩容，并追加数据
*
* @param array
* @param value
*/
private static int[] appendBucket(int[] array, int value) {
array = Arrays.copyOf(array, array.length + 1);
array[array.length - 1] = value;
return array;
}
基数排序总结
计数排序、桶排序、基数排序这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
总结
