Java基础知识强化51:经典排序之桶排序(BucketSort)

1. 首先说明三点:

(1)桶排序是稳定的

(2)桶排序是常见排序里最快的一种,比快排还要快…大多数情况下

(3)桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法

2. 桶排序的分析过程:

对无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9],考试分数为1-100等

例如待排数字[6,2,4,1,5,9]

准备10个空桶(桶数是固定区间中最大数,比如这里就是10)

[6 2 4 1 5 9]               待排数组

[0 0 0 0 0 0 0 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

(1)顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]

[6 2 4 1 5 9]             待排数组

[0 0 0 0 0 0 6 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

(2)顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶:

[6 2 4 1 5 9]               待排数组

[0 0 2 0 0 0 6 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

(3)4,5,6省略,过程一样,全部入桶后变成下边这样:

[6 2 4 1 5 9]               待排数组

[0 1 2 0 4 5 6 0 0 9]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

 

0表示空桶,跳过,顺序取出即可:1 2 4 5 6 9

Java基础知识强化51:经典排序之桶排序(BucketSort)

3. 桶排序代码实现:

 /* package whatever; // don't place package name! */

 import java.util.*;
import java.lang.*;
import java.io.*; /* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[] Array = { 99, 65, 24, 47, 50, 88,33, 66, 67, 31, 18 };
int[] newArray = bucketSort(Array,99);
printArray(newArray);
} public static int[] bucketSort(int[] array,int maxNumber) {
int[] newArray = new int[maxNumber + 1]; for(int i=0; i<array.length; i++) {
newArray[array[i]] = array[i]; } return newArray;
} // 打印功能
public static void printArray(int[] arr) {
System.out.print("[");
for (int x = 0; x < arr.length; x++) { if(arr[x] >0) {
System.out.print(arr[x]+" ");
}
}
System.out.println("]");
}
}

运行效果,如下:

Java基础知识强化51:经典排序之桶排序(BucketSort)

上一篇:Java基础知识强化之IO流笔记52:IO流练习之 把一个文件中的字符串排序后再写入另一个文件案例


下一篇:Java基础知识强化之集合框架笔记69:Collections类之ArrayList存储自自定义对象并排序的案例