之前了解的排序选择排序、
冒泡排序、
插入排序、
归并排序、
快速排序
都是基于比较的排序，而桶排序提出了一种新的思路，即基于数据状态的排序。
桶排序思想下的排序
- 计数排序
- 基数排序
桶排序的特点
- 桶排序思想下的排序都是不基于比较的排序
- 时间复杂度为O(N)，额外空间负载度O(M)
- 应用范围有限，需要样本的数据状况满足桶的划分
经典的 计数排序和基数排序 对样本的要求
- 一般来讲，计数排序要求，样本是整数，且范围比较窄
- 一般来讲，基数排序要求，样本是10进制的正整数
桶排序的思想
- 得到无序数组的取值范围
2.根据取值范围"创建"对应数量的"桶"
3.遍历数组，把每个元素放到对应的"桶"中.
4.按照顺序遍历桶中的每个元素，依次放到数组中，即可完成数组的排序。
"桶"是一种容器，这个容器可以用多种数据结构实现，包括数组、队列或者栈。
计数排序
图解
1.找出无序数组的最大值，创建一个长度为最大值+1的空数组
2.遍历原数组，统计每个元素出现的次数
3.遍历"桶"，即用于元素个数统计的数组，得到有序的数组
代码
public static void countSort(int[] arr){
if (arr == null ||arr.length<2){
return;
}
//找到数组中最大的数
int max = Integer.MIN_VALUE;
for (int i =0;i<arr.length;i++){
max = Math.max(max,arr[i]);
}
//实例化一组桶
int[] bucket = new int[max+1];
//把数组中的数放到自己的桶中
for (int i=0;i<arr.length;i++){
bucket[arr[i]]++;
}
//按照桶的顺序把数倒出来
int i=0;
for (int j=0;j<bucket.length;j++){
while (bucket[j]-->0){
arr[i++]=j;
}
}
}
复制代码经典的基数排序
其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机 (Tabulation Machine)上的贡献。
基数排序法会使用到桶 (Bucket)，顾名思义，通过将要比较的位（个位、十位、百位…），将要排序的元素分配至 0~9 个桶中，借以达到排序的作用，在某些时候，基数排序法的效率高于其它的比较性排序法。
算法步骤
- 找到数据中最大的一个数，确定排序数组中的最大位。
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
- 从最低位开始，依次进行一次排序
- 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
动画演示
图解
以下数组为例
int[] arrays = {6, 4322, 432, 344, 55 };
复制代码现在我们有10个桶子，每个桶子下能装载arrays.length个数字..
int[][] buckets = new int[arrays.length][10];
复制代码1.将数组的每个【个位数】进行分配到不同的桶子上：
分配完之后，我们按照顺序来进行回收：得到的结果应该是这样子的：{4322,432,344,55,6}
2.将数组的每个【十位数】进行分配到不同的桶子上(像6这样的数，往前边补0)：
分配完之后，我们按照顺序来进行回收：得到的结果应该是这样子的：{6,4322,432,344,55}
3.将数组的每个【百位数】进行分配到不同的桶子上(像6、55这样的数，往前边补0)：
分配完之后，我们按照顺序来进行回收：得到的结果应该是这样子的：{6,55,4322,344,432}
4.将数组的每个【千位数】进行分配到不同的桶子上(像6、55这样的数，往前边补0)
分配完之后，我们按照顺序来进行回收：得到的结果应该是这样子的：{6,55,344,432,4322}
代码
public static int findMax(int[] arrays) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arrays.length; i++) {
max = Math.max(max, arrays[i]);
}
return max;
}
public static void radixSort(int[] arrays) {
int max = findMax(arrays);
//需要遍历的次数由数组最大值的位数来决定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10];
//获取每一位数字(个、十、百、千位...分配到桶子里)
for (int j = 0; j < arrays.length; j++) {
int num = (arrays[j] / i) % 10;
//将其放入桶子里
buckets[j][num] = arrays[j];
}
//回收桶子里的元素
int k = 0;
//有10个桶
for (int j = 0; j < 10; j++) {
//对每个桶子里的元素进行回收
for (int l = 0; l < arrays.length ; l++) {
//如果桶子里面有元素就回收(数据初始化会为0)
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j];
}
}
}
}
}
复制代码升级版的基数排序
经典的基数排序需要额外的栈或者队列，其实可以用 每一位数出现的次数和遍历的顺序来达到同样的效果。
图解
代码
public static void radixSortPlus(int[] arr){
if (arr == null ||arr.length<2){
return;
}
radixSortPlus(arr,0,arr.length-1,maxbits(arr));
}
//arr[l..r]排序 , digit 数组中最大的位数
public static void radixSortPlus(int[] arr,int L,int R,int digit){
final int radix = 10;
int i=0;
int j=0;
//有多少个数就准备多少个辅助空间
int[] help = new int[R-L+1];
for (int d=1;d<=digit;d++){ // 最大多少位，就进出多少次
// 10个空间
// count[0] 当前位(d位)是0的数字有多少个
// count[1] 当前位(d位)是(0和1)的数字有多少个
// count[2] 当前位(d位)是(0、1和2)的数字有多少个
// count[i] 当前位(d位)是(0~i)的数字有多少个
int[] count = new int[radix]; // count[0..9]
for (i=L;i<=R;i++){
j = getDigit(arr[i],d);//得到当前位置上的数
count[j]++;
}
//把count 数组变成累加和的形式
for (i=1;i<radix;i++){
count[i] = count[i]+count[i-1];
}
//从右往左遍历
for (i=R;i>=L;i--){
j = getDigit(arr[i],d);
help[count[j]-1] =arr[i];
count[j]--;
}
for (i = L, j = 0; i <= R; i++, j++) {
arr[i] = help[j];
}
}
}
public static int getDigit(int x,int d){
//x /10 的几次方 然后和10 取模，得到该位置上的数
return ((x/((int)Math.pow(10,d-1)))%10);
}
复制代码ps:部分图片来源网络，侵删。
排序总结
稳定性
排序算法总结
- 1）不基于比较的排序，对样本数据有严格要求，不易改写
- 2）基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
- 3）基于比较的排序，时间复杂度的极限是O(N*logN)
- 4）时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。
- 5）为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并
近期评论