【排序】桶排序 bucket sort

目录

 

1.桶排序思想

2.算法过程

3.算法实现代码

 

在开头安利一个可视化网站:

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

这上面有排序算法的可视化实现,可结合下文算法过程对照着图学习。

【排序】桶排序 bucket sort

    1. 思想:
      将待排序集合中处于同一值域的元素存入同一个桶中,
      这样的话,集合中的元素就被拆分成多个桶,再对每个桶中的元素排序,再将有序的桶放回原集合中。
       一句话:通过“分配”和“收集”实现排序。
      Notes:
      (1).桶排序是对计数排序的改进。计数排序是给每一个元素都开辟空间,记录出现次数,以达到排序。
      所以,对于数值过大的元素或者浮点数,计数排序就不能很很好的解决。
      所以应用桶排序,可以很好的解决,根据元素的分布利用一个hash函数将值域相同的元素放到一个桶。
      (2).桶排序的时间复杂度O(N)~O(N*logN),N为元素个数。
      (3).桶排序适用于元素均匀分布的情况。

    2. 算法过程:
      (1).搭建桶的结构,使用单链表;
      (2).hash函数定义:即如何确定元素是否在同一值域中,

             (value * len) / (max_value + 1);
      value:当前计算的元素
      len:待排序集合的长度
      max_value:集合中数值最大的元素
      (3).桶中元素排序:链表中元素的插入;
      (4).出桶,排序输出。

      3.代码

【排序】桶排序 bucket sort
public class buket_sort {

  public static void main(String[] args) {
    int[] arr={10,7,4,8,2,6,5,9,4};
    System.out.println( "begin..." + Arrays.toString( arr ) );
    new buket_sort().sort( arr );
    System.out.println( "final..." + Arrays.toString( arr ) );

  }
  /**
   * (value * len) / (max_value + 1)
   * 返回元素对应的桶的下标
   * @param value
   * @param length
   * @param max
   * @return
   */
  public static int hash(int value,int length,int max_value){
    return (value * length) / (max_value + 1);
  }

  /**
   * 排序实现
   * @param arr
   */

  public static void sort(int []arr){
    int len=arr.length;
    LinkedNode[] bucket=new LinkedNode[len];//桶的个数可以是元素个数
    int max=getMax(arr);
//    System.out.println(max);
    //入桶
    for (int i = 0; i < len; i++) {
      int value=arr[i];
      int index=hash(value, len, max);
      if(bucket[index] == null){
        bucket[index]=new LinkedNode(value);
      }else{
        insertInto(value,bucket[index],bucket,index);
      }
    }
    //出桶
    int k=0;
    for(LinkedNode node :bucket){
      if(node!=null){
        while(node!=null){
          arr[k++]=node.value;
          node=node.next;
        }
      }
    }
  }
  /**
   * 桶内元素排序
   * 如果该元素小于头节点,替换头节点
   * 如果大于,向后走,或插入到末尾或中间
   * @param value 待排序元素值
   * @param linkedNode 桶元素中头节点
   * @param bucket 用于替换头节点
   * @param index 下标
   */
  private static void insertInto(int value, LinkedNode head,
      LinkedNode[] bucket, int index) {
    LinkedNode newNode=new LinkedNode(value);//备份节点
    if(value<=head.value){//替换头节点
      newNode.next=head;
      bucket[index]=newNode;
      return;
    }
    LinkedNode p=head;
    LinkedNode pre=p;//当前节点的前一个节点
    while(p != null && value>p.value){
      pre=p;
      p=p.next;
    }
    if(p==null){
      pre.next=newNode;
    }else{
      pre.next=newNode;
      newNode.next=p;
    }  
  }
  /**
   * 得到数组中最大的元素。
   * 
   * @param arr
   * @return
   */
  private static int getMax(int[] arr) {
    int max=Integer.MIN_VALUE;
    int len=arr.length;
    for (int i = 0; i < len; i++) {
      if(arr[i]>max){
        max=arr[i];
      }
    }
    return max;
  }
}
bucket sort

节点的框架

 

【排序】桶排序 bucket sort
public class LinkedNode {
  public int value;
  public LinkedNode next;

  public LinkedNode(int value){
    this.value=value;
  }
}
LinkedNode

 

       实现结果:

  【排序】桶排序 bucket sort

 

上一篇:Elasticsearch Bucket & Metric 聚合分析及嵌套聚合


下一篇:2021.1.31 刷题(前K个高频元素-桶排序)