三大线性排序之桶排序
添加时间:2013-7-25 点击量:
一.概念引入
有作者把计数排序也称为桶排序（各个桶中元素的排序采取计数排序），获得数组C后直接畴前去后遍历，输出数组值次数组下标，为0就不输出（或者存入原数组，不稳定），不过笔者认为这种说法不严谨（一个很明显的题目是输出会是双重for轮回，不过也有那个意思，叫鸽巢排序也未尝不成），因为桶排序请求输入数据在[0，1）局限内（计数排序请求整数），先把区间[0，1）划分成n个雷同大小的子区间，称为桶，然后将n个输入数分布到各个桶中去。因为输入数均匀且自力分布在[0，1）上，所以，一般不会有很多半落在一个桶中的景象。为了获得成果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来。
附上鸽巢排序核心源代码：
public void pigeonSort（int[] array， int max） {
int[] c = new int[max];//max是array数组中的最大值
for（int i=0; i<array.length; i++）
c[array[i]]++;
//c数组只是统计元素呈现次数
int k = 0;
for（int i=0; i<max; i++）
for（int j=1; j<=c[i]; j++）
array[k++] = i;
}
二.算法描述
例如要对大小为[1..1000]局限内的n个整数A[1..n]排序，可以把桶设为大小为10的局限，具体而言，设凑集B[1]存储[1..10]的整数，凑集B[2]存储（10..20]的整数，……凑集B[i]存储（（i-1）10， i10]的整数，i = 1，2，..100。统共有100个桶。然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，甚至快排，一般来说任何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，如许就获得所稀有字排好序的一个序列了。
下图默示出了桶排序感化于有10个数的输入数组上的操纵过程。
三.算法的Java实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
public class BucketSort {
public static void bucketSort（double array[]） {
int length = array.length;
ArrayList arrList[] = new ArrayList[length];
/
每个桶是一个list，存放落在此桶上的元素
前次的基数排序我采取的是计数排序实现的，其实也可以用下面的办法，有爱好的读者不妨一试（我认为太错杂）
不过效力估计不高（采取了动态数组）
/
//划分桶并填元素
for （int i = 0; i < length; i++） {
//0.7到0.79放在第8个桶里，编号7；第一个桶放0到0.09
int temp = （int） Math.floor（10 array[i]）;
if （null == arrList[temp]）
arrList[temp] = new ArrayList（）;
arrList[temp].add（array[i]）;
}
// 对每个桶中的数进行插入排序
for （int i = 0; i < length; i++） {
if （null != arrList[i]） {
//此处排序办法不定，不过越快越好，除了三大线性排序外，都没有Collections
//和Arrays里的sort好，因为这是调优后的快拍
//Arrays里也有，在基数排序里用过copyOf和fill办法
Collections.sort（arrList[i]）;
}
}
//输出类似鸽巢排序
int count = 0;
for （int i = 0; i < length; i++） {
if （null != arrList[i]） {
Iterator iter = arrList[i].iterator（）;
while （iter.hasNext（）） {
Double d = （Double） iter.next（）;
array[count] = d;
count++;
}
}
}
}
/
每个元素满足0<=array[i]<1，貌似还要长度雷同，
若是雷同小数位（digit），则可以把小数搞为整数，最后再除以10^digit
可以Random.nextInt（101）/100
/
public static void main（String[] args） {
double array[] = { 0.78， 0.17， 0.39， 0.26， 0.72， 0.94， 0.21， 0.12，
0.23， 0.68 };
bucketSort（array）;
for （int i = 0; i < array.length; i++）
System.out.print（array[i] + ）;
System.out.println（）;
}
}
四.算法应用
在口试的海量数据处理惩罚题目中，如对天天数以亿计的数据进行排序，直接排序即使采取nlgn的算法，依然是一件很可骇的工作，内存也无法容纳如此多的数据，这时桶排序就可以有效地降落数据的数量级，再对降落了数量级的数据进行排序，可以获得斗劲杰出的结果。别的也有说桶排序对元组排序，小我认为还是基数排序处理惩罚元组斗劲好，毕竟?成果本身就是多关键字排序，只须要把斗劲单个数字（有爱好的参看我的这一篇《基于计数排序的基数排序》http://www.cnblogs.com/hxsyl/p/3210647.html）换成斗劲单个元组元素就好。
所有随风而逝的都属于昨天的，所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》
所有随风而逝的都属于昨天的，所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》一.概念引入
有作者把计数排序也称为桶排序（各个桶中元素的排序采取计数排序），获得数组C后直接畴前去后遍历，输出数组值次数组下标，为0就不输出（或者存入原数组，不稳定），不过笔者认为这种说法不严谨（一个很明显的题目是输出会是双重for轮回，不过也有那个意思，叫鸽巢排序也未尝不成），因为桶排序请求输入数据在[0，1）局限内（计数排序请求整数），先把区间[0，1）划分成n个雷同大小的子区间，称为桶，然后将n个输入数分布到各个桶中去。因为输入数均匀且自力分布在[0，1）上，所以，一般不会有很多半落在一个桶中的景象。为了获得成果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来。
附上鸽巢排序核心源代码：
public void pigeonSort（int[] array， int max） {
int[] c = new int[max];//max是array数组中的最大值
for（int i=0; i<array.length; i++）
c[array[i]]++;
//c数组只是统计元素呈现次数
int k = 0;
for（int i=0; i<max; i++）
for（int j=1; j<=c[i]; j++）
array[k++] = i;
}二.算法描述
例如要对大小为[1..1000]局限内的n个整数A[1..n]排序，可以把桶设为大小为10的局限，具体而言，设凑集B[1]存储[1..10]的整数，凑集B[2]存储（10..20]的整数，……凑集B[i]存储（（i-1）10， i10]的整数，i = 1，2，..100。统共有100个桶。然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，甚至快排，一般来说任何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，如许就获得所稀有字排好序的一个序列了。
下图默示出了桶排序感化于有10个数的输入数组上的操纵过程。
三.算法的Java实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
public class BucketSort {
public static void bucketSort（double array[]） {
int length = array.length;
ArrayList arrList[] = new ArrayList[length];
/
每个桶是一个list，存放落在此桶上的元素
前次的基数排序我采取的是计数排序实现的，其实也可以用下面的办法，有爱好的读者不妨一试（我认为太错杂）
不过效力估计不高（采取了动态数组）
/
//划分桶并填元素
for （int i = 0; i < length; i++） {
//0.7到0.79放在第8个桶里，编号7；第一个桶放0到0.09
int temp = （int） Math.floor（10 array[i]）;
if （null == arrList[temp]）
arrList[temp] = new ArrayList（）;
arrList[temp].add（array[i]）;
}
// 对每个桶中的数进行插入排序
for （int i = 0; i < length; i++） {
if （null != arrList[i]） {
//此处排序办法不定，不过越快越好，除了三大线性排序外，都没有Collections
//和Arrays里的sort好，因为这是调优后的快拍
//Arrays里也有，在基数排序里用过copyOf和fill办法
Collections.sort（arrList[i]）;
}
}
//输出类似鸽巢排序
int count = 0;
for （int i = 0; i < length; i++） {
if （null != arrList[i]） {
Iterator iter = arrList[i].iterator（）;
while （iter.hasNext（）） {
Double d = （Double） iter.next（）;
array[count] = d;
count++;
}
}
}
}
/
每个元素满足0<=array[i]<1，貌似还要长度雷同，
若是雷同小数位（digit），则可以把小数搞为整数，最后再除以10^digit
可以Random.nextInt（101）/100
/
public static void main（String[] args） {
double array[] = { 0.78， 0.17， 0.39， 0.26， 0.72， 0.94， 0.21， 0.12，
0.23， 0.68 };
bucketSort（array）;
for （int i = 0; i < array.length; i++）
System.out.print（array[i] + ）;
System.out.println（）;
}
}四.算法应用
在口试的海量数据处理惩罚题目中，如对天天数以亿计的数据进行排序，直接排序即使采取nlgn的算法，依然是一件很可骇的工作，内存也无法容纳如此多的数据，这时桶排序就可以有效地降落数据的数量级，再对降落了数量级的数据进行排序，可以获得斗劲杰出的结果。别的也有说桶排序对元组排序，小我认为还是基数排序处理惩罚元组斗劲好，毕竟?成果本身就是多关键字排序，只须要把斗劲单个数字（有爱好的参看我的这一篇《基于计数排序的基数排序》http://www.cnblogs.com/hxsyl/p/3210647.html）换成斗劲单个元组元素就好。
