算法学习一、Java桶排序算法



具体代码如下,注释中说的很清楚了,不解释,直接看代码:o8C思考者日记网-束洋洋个人博客

package com.shyy.algorithms;  
  
import java.util.ArrayList;  
import java.util.Iterator;  
  
/** 
 * 桶排序算法学习 
 * 原理:每个数固定到相应的位置,最后进行顺序输出 
 * 缺点:耗内存 
 * @author shuYangYang 
 * @email:shuyangyang@aliyun.com 
 * @website:www.shuyangyang.com.cn 
 */  
public class BucketSort {  
  
    /** 
     * 测试..... 这里的测试数据是一个含n个元素的数组,且每个元素满足0<=arr[i]<1 
     */  
    public static void main(String[] args) {  
        double arr[] = { 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68 ,0.13, 0.13};  
        bucketSort(arr);  
        System.out.print("最终排序结果:");  
        for (int i = 0; i < arr.length; i++) {  
            System.out.print(arr[i]+"t");  
        }  
    }  
  
    /** 
     * 桶排序算法,对arr进行桶排序,排序结果仍放在arr中 
     *  
     * @param arr 
     */  
    @SuppressWarnings({ "rawtypes", "unchecked" })  
    private static void bucketSort(double arr[]) {  
        int n = arr.length;  
        ArrayList arrList[] = new ArrayList[n];  
        // 把arr中的数均匀的的分布到[0,1)上,每个桶是一个list,存放落在此桶上的元素  
        for (int i = 0; i < n; i++) {  
            int temp = (int) Math.floor(n * arr[i]); //返回不大于的最大整数  
            if (null == arrList[temp]){  
                arrList[temp] = new ArrayList();  
            }  
            arrList[temp].add(arr[i]);  
        }  
        // 对每个桶中的数进行插入排序  
        for (int i = 0; i < n; i++) {  
            if (null != arrList[i]){  
                insert(arrList[i]);  
            }  
        }  
        // 把各个桶的排序结果合并  
        int count = 0;  
        for (int i = 0; i < n; i++) {  
            if (null != arrList[i]) {  
                Iterator iter = arrList[i].iterator();  
                while (iter.hasNext()) {  
                    Double d = (Double) iter.next();  
                    arr[count] = d;  
                    count++;  
                }  
            }  
        }  
    }  
  
    /** 
     * 用插入排序对每个桶进行排序 
     *  
     * @param list 
     */  
    @SuppressWarnings({ "unchecked", "rawtypes" })  
    private static void insert(ArrayList list) {  
        if (list.size() > 1) {  
            for (int i = 1; i < list.size(); i++) {  
                if ((Double) list.get(i) < (Double) list.get(i - 1)) {  
                    double temp = (Double) list.get(i);  
                    int j = i - 1;  
                    for (; j >= 0 && ((Double) list.get(j) > (Double) list.get(j + 1)); j--){  
                        list.set(j + 1, list.get(j));  
                    }  
                    list.set(j + 1, temp);  
                }  
            }  
        }  
    }  
} 

 o8C思考者日记网-束洋洋个人博客

 o8C思考者日记网-束洋洋个人博客

 

(转载本站文章请注明作者和出处 思考者日记网|束洋洋个人博客 ,请勿用于任何商业用途)

『访问 思考者日记网404页面 寻找遗失儿童』

告知
  •     本站90%以上文章均属原创,部分转载已加上原作者出处。 如需转载本站文章请您务必保留本站出处!
  •     打广告评论者请自重,请为广大网友提供一个健康干净的网络空间。
  •  感谢主机屋提供网站空间;
  •  感谢万网阿里云提供域名解析;
  •  感谢EmpireCMS提供CMS系统;
  •  感谢bootstrap展示本站前端页面;
  •  感谢Glyphicons Halflings提供字体;
  •  感谢大家一直以来对本站的喜爱,感谢大家!
近期文章 建议与反馈

 

网友评论
我也来说两句
点击显示

 

点击显示弹幕