排序算法之桶排序

---

排序之桶排序

通过散列索引加链表 来进行排序 适用于分布相对均匀的数据。算法优劣依赖于hash函数 （不多废话 上代码）

代码实现

代码如下（示例）：

package com.MySort;

import com.MyFunctions.GetRodomArrays;
import com.MyFunctions.MaxAndMinOfArr;

import java.util.Arrays;

public class BucketSort {
//    获得hash函数
    public static int hash(int element, int max, int length) {
//        相对简单的一个散列函数
        return (element * length) / (max + 1);
    }

    public static void main(String[] args) {
//        这是自己写的随机数组方法  获取不重复的随机数组 元素最大15 长度是10；
        int arr[] = GetRodomArrays.acquireUniqueArr(15, 10);
//        int arr[] = {5, 1, 12, 3, 6, 4, 9, 10, 14, 11};
        System.out.println(Arrays.toString(arr));
        bucket_Sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void bucket_Sort(int[] arr) {
        int length = arr.length;
        LinkedNode[] bucket = new LinkedNode[length + 1];
        int max = MaxAndMinOfArr.maxOfarr(arr);
        for (int i = 0; i < length; i++) {
//            获得索引
            int hash = hash(arr[i], max, length);
//           如果该桶是空的
            if (bucket[hash] == null) {
//                直接将元素放入桶中
                bucket[hash] = new LinkedNode(arr[i]);
            } else {
//                桶里面有元素 那么就执行相应的入桶方法
                insertInto(arr[i], bucket[hash], bucket, hash);
            }
        }
        int k = 0;
        for (LinkedNode node:bucket) {
            while(node!=null){
                arr[k++] = node.val;
                node = node.next;
            }
        }
    }
//入桶方法
    private static void insertInto(int value, LinkedNode head, LinkedNode[] node, int hash) {
//  也就是说从当前链表找到自己的位置 要求：如果当前的值小于头节点 就替换头节点
//  然后旧的头节点需要往后寻找自己的位置
        LinkedNode newnode = new LinkedNode(value);
        if(value<= head.val){
//            替换头节点 然后放在头上
            newnode.next = head;
//            后面依次不动排好 替换头节点
            node[hash] = newnode;
            return;
        }
//       程序走到这里 说明当前的值小于头节点
//        备份一份头节点
        LinkedNode  p =head;
//        生成前驱节点
        LinkedNode  pre =p;
//       如果说p不为空 并且value小于当前节点的值 就往后找合适的位置 也就是大于当前值的第一个节点
        while(p!=null&&value>p.val){
            pre = p;
            p=p.next;
        }
//        这个while循环走完 说明要么p指针已经走到了合适的位置，要么p已经为空（当前的值应该放到当前链表最后）
        if(p==null){
//          如果走到了最后 那么将节点的指针 直接连到这个位置即可
            p = newnode;
//          这里要记得加上链接关系 第一次写代码的时候没有发现这里的bug（憨憨落泪）
            pre.next=p;
        }else{
//           否则不是最后一个
//           要在当前p的位置进行插入 那么就获取取得前一个节点
//            前一个节点的next指向当前的新节点
            pre.next =newnode;
//          后面的节点不要落下
            newnode.next=p;
        }
        }

    }

---

注释详细：记录学习~