桶排序与基数排序

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;

}

未完后面待续

桶排序与基数排序

相关推荐