架构师面试系列-桶排序

墨蓝 2023-02-20 03:15 7阅读 0赞

/** * 桶排序 * * * * 1、先找到数组中的最大值和最小值，然后根据桶数，计算出每个桶中的数据范围 * * 2、遍历原始数据，先找到该数据对应的桶序列，然后将该数据放在对应序列的桶中。 * * 3、当向同一个序列的桶中第二次插入数据时，判断桶中已存在的数字与新插入的数字的大小，按从左到右，从小到大的顺序插入。一般使用链表来存储桶中的数据。 * * 4、全部数据装桶完毕后，按序列，从小到大合并所有非空的桶。 * * 5、合并之后就是排好序的数据 * * 动画演示地址： * * https://www.cs.usfca.edu/~galles/visualization/BucketSort.html * */
    public class BucketSort { 
    
        public double[] sort(double[] sourceArray){ 
            double[] arr= Arrays.copyOf(sourceArray,sourceArray.length);
             return bucketSort(arr,5);
        }
    
        private double[] bucketSort(double[] arr,int buckerSize){ 
            int len=arr.length;
            double[] result=new double[len];
            double min=arr[0];
            double max=arr[0];
            //找到最大值和最小值
            for(int i=0;i<arr.length;i++){ 
                min=min<=arr[i]?min:arr[i];
                max=max>=arr[i]?max:arr[i];
            }
            //每个桶的空间的容量 ((最大值-最小值)+1)/buckerSize(桶排序的总长度)
            double space=(max-min+1)/buckerSize;
            //先创建好每一个桶空间
            ArrayList<Double>[] arrayLists=new ArrayList[buckerSize];
    
            for(int i=0;i<len;i++){ 
                //找到待排序所在的位置。
                int index=(int)Math.floor((arr[i]-min)/space);
                if(arrayLists[index]==null){ 
                    //链表中没有东西直接插入
                    arrayLists[index]=new ArrayList<Double>();
                    arrayLists[index].add(arr[i]);
                }else{ 
                    //链表的排序
                    int k=arrayLists[index].size()-1;
                    while(k>=0 && (Double)arrayLists[index].get(k)>arr[i]){ 
                        if(k+1>arrayLists[index].size()-1){ 
                            arrayLists[index].add(arrayLists[index].get(k));
                        }else { 
                            arrayLists[index].set(k+1,arrayLists[index].get(k));
                        }
                        k--;
                    }
                    if (k + 1 > arrayLists[index].size() - 1) { 
                        arrayLists[index].add(arr[i]);
                    } else { 
                        arrayLists[index].set(k + 1, arr[i]);
                    }
                }
            }
            //把各个桶的排序结果合并 ,count是当前的数组下标
            int count = 0;
            for (int i = 0; i < buckerSize; i++) { 
                if (null != arrayLists[i] && arrayLists[i].size() > 0) { 
                    Iterator< Double > iter = arrayLists[i].iterator();
                    while (iter.hasNext()) { 
                        Double d = (Double) iter.next();
                        result[count] = d;
                        count++;
                    }
                }
            }
            return result;
        }
    
        public static void main(String[] args) { 
            double[] arrdoublescore={ 2,3,2,4,3,234,23,4};
            BucketSort bucketSort=new BucketSort();
            Arrays.stream(bucketSort.sort(arrdoublescore)).forEach(System.out::println);
        }
    }