桶排序与基数排序

桶排序：限定场景在0-n 有数值范围内一个无序数列a[k]，对无序数列进行分n+1个桶，然后从桶中比较获取回来一个有序数列。

排序方法：1、建立0-n数值的（n+1）一个桶，然后对无序数列中的a[k]等于对应桶（n）的数值进行累加统计 2、 遍历整个桶，数值和桶对应编号（n）相等的进行赋值给新的数列，并对其桶统计值自减，直至为0. 这样得出来就是一个有序的数列。

桶排序举个例子，有一个整数序列，0, 133, 45, 386, 106，45下面是排序过程：

1、首先计算出最大桶，最大桶是386；

2、对不同的桶进行统计，{1（桶编号0只有1个数值），0(桶编号为1没有数值,.................2（b编号45 含有2个数值）,..............1(编号386)}

3、最后对桶进行遍历 ，桶含有值的 依次装入 一个新的序列数组中{0, 45,45, 106, 133, 386} 完成排序

基数排序：核心思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。

排序方法：比如有个数列{123,456，78}。我们可以通过获取最大数值的位数，通过对不足的前面补0，然后对这个序列进行个位、十位、百位的0-9进行分桶 进行排序，最后得出来就是个有序数列。

基数排序这儿思考一个问题，为什么将整数按位数进行切割后，按照位数进行排序，不使用冒泡、快速排序这些算法呢。认真想下，其实比较简单，冒泡算法还是快速排序本来就比桶排序比较来说，长的很多，按位数进行排序后，对其做冒泡排序，时间复杂度等于 K（总位数）* n*(n-1) ，比原来的冒泡排序还更复杂了，这样还不如就直接使用冒泡排序就可以直接一次完成排序，快速排序也有同样差不多道理，桶排序就是因为时间效率远远大的多于比如冒泡、快速排序，所以其实这儿基数排序相对说是桶排序的一个折中 空间和时间复杂度的算法。

基数排序举个例子，有一个整数序列，0, 133, 45, 386, 106，下面是排序过程：

第一次排序，个位，000 133 045 386 106，无任何变化

第二次排序，十位，000 106 133 045 386

第三次排序，百位，000 045 106 133 386

最终结果，0, 45, 106, 133, 386, 排序完成。

下面附桶排序和基数排序个人实现代码：

private static int[] bucketSort(int[] array) {

int max = 0;

for(int i=0;i<array.length;i++){

if(max<array[i]){

max= array[i];

}

}

max += 1; //计算得出桶最大值，确定最大桶

int[] data = new int[array.length];

int[] bucket = new int[max];

for (int i = 0; i < array.length; i++) {//n

bucket[array[i]]++; // 对数列中进行装桶

}

int i = 0;

int j = 0;

while (i < max) {// 遍历所有桶中含有 统计数值大于0的数值，进行有序装载对应的数据，最后出来有序数列

if (bucket[i] > 0) {

while ((bucket[i]--) > 0) {

data[j++] = i;

}

}

i++;

}

return data;

}

//基数排序

public static void radixSort(int[] data) {

int length = data.length;

// 获取指数的位数

int count = getMaxCount(data, length); //获取最大位数

// 对各个位数进行排序

int index = 0;//

while (index < count) {

data = bucketSort(data, index, count);

index++;

}

}

private static int getMaxCount(int[] data, int length) {

int max = 0;

for (int i = 0; i < length; i++) {

if (data[i] > max) {

max = data[i];

}

}

int count = 1;

int n = 10;

while (max / n != 0) {// 1021 ,20

n = n * 10;

count++;

}

return count;

}

//按位数进行桶排序

private static int[] bucketSort2(int[] array, int index, int count) {

int bucketLength = 10;

int multiNum = (int) Math.pow(10, index);

int[] data = new int[array.length];

int[] bucket = new int[bucketLength];

int i;

for (i = 0; i < array.length; i++) {// n

// array 数据转化为到具体位数进行排序

int temp = (array[i] / multiNum) % 10;

bucket[temp]++;

}

for (i = 1; i < 10; i++) {

bucket[i] += bucket[i - 1];

}

for (i = array.length - 1; i >= 0; i--) {

data[bucket[(array[i] / multiNum) % 10] - 1] = array[i];

bucket[(array[i] / multiNum) % 10]--;

}

for (i = 0; i < array.length; i++) {

array[i] = data[i];

}

return array;

}

未完后面待续