SystemArchitect 2018-10-13
桶排序:限定场景在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;
}
未完后面待续