桶排序
1.问题描述：使用桶排序算法对控制台输入的数字进行排序
2. 桶排序涉及到几个问题：
1.桶的大小，这里我们可以根据输入的元素的个数来确定桶的大小
2.怎么确定当前元素进入哪一个桶，这里我们使用到的是通过一个哈希函数来进行计算
int index = (element * length) / (max + 1);
element为当前元素的值，length为桶的大小，max为数组中最大元素的值
③因为输入的数据是随机的，所以有可能在一个桶中分布着好几个数据
所以我们可以使用动态的数据结构来存储，考虑到插入的操作是比较频繁的，所以这里我们使用链表来进行插入元素，并且在一个桶中维持从小到大的顺序
在一开始的时候我们扫描桶的元素，找到第一个比当前需要插入的元素大或者相等的的元素，那么将这个元素往前插入就可以了
了解了上面的问题就可以写代码了
代码:
public class ListNode {
int data;
ListNode next;
public ListNode(int data){
this.data = data;
}
}
public class Util {
public static int maxOf(int[] arr)
{
int max = arr[0];
for(int i = 1;i<arr.length;i++)
{
if(max < arr[i])
{
max = arr[i];
}
}
return max;
}
}
import java.util.Arrays;
public class BucketSort {
//根据桶的个数来确定哈希函数，这份代码适合桶的个数等于数组长度
//根据哈希函数来确定每个元素所在桶的索引
private static int hash(int element,int max,int length)
{
return (element*length)/(max+1);
}
public static void main(String[] args)
{
int[] arr = {1,9,8,6,5,3,2};
System.out.println(Arrays.toString(arr));
new BucketSort().sort(arr);
System.out.println(Arrays.toString(arr));
}
//排序 桶的个数等于数组长度
private void sort(int[] arr)
{
int length = arr.length;
ListNode[] bucket = new ListNode[length]; //桶的个数
int max = Util.maxOf(arr); //求max
//入桶
for(int i = 0;i < length;i++)
{
int value = arr[i]; //扫描每一个元素
int index = hash(value,max,length); //桶的下标
if(bucket[index] == null)
{
bucket[index] = new ListNode(value);
}
else{
insertInto(value,bucket[index],bucket,index);//插入链表
}
}
int k = 0;//记录数组下标
//出桶
for(ListNode node :bucket)
{
if(node != null)
{
while(node != null)
{
arr[k++] = node.data;
node = node.next;
}
}
}
}
//向每个桶中添加元素
private void insertInto(int value,ListNode head,ListNode[] bucket,int index)
{
ListNode newNode = new ListNode(value);
if(value <= head.data)
{
newNode.next = head;
//替换头节点
bucket[index] = newNode;
return;
}
ListNode p = head;
ListNode pre = p;
while(p != null)
{
if(value > p.data)
{
pre = p;
p = p.next;
if(p == null)
{
p = newNode;
}
}
else if(p!=head && value > p.data){
//插在pre和p之间
pre.next = newNode;
newNode.next = p;
}
}
}
}
测试结果如下:
[1, 9, 8, 6, 5, 3, 2]
[1, 2, 3, 5, 6, 8, 9]
| 
转播
