当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

堆排序的应用:从1亿条数据中从大到小取前10000条

发表于: 2012-09-20   作者:128kj   来源:转载   浏览:
摘要: 堆排序的应用:从1亿条数据中从大到小取前10000条 import java.util.Arrays; import java.util.Date; import java.util.Random; public class Top10000{ public static void main(String[] args) {
堆排序的应用:从1亿条数据中从大到小取前10000条
import java.util.Arrays;  
import java.util.Date;  
import java.util.Random;  
  
public class Top10000{  
      
    public static void main(String[] args) {  
        find();  
    }  
    public static void find( ) {//  
        int number = 1000000000;// 一亿条数据  
        int maxnum = 1000000000;// 数据最大值  
        int i = 0;  
        int topnum = 10000;// 从大到小取多少条  
       
        Date startTime = new Date();  
          
        Random random = new Random();  
        int[] top = new int[topnum];  
        for (i = 0; i < topnum; i++) {  
            top[i] = Math.abs(random.nextInt(maxnum));//设置为随机数  
        }  
  
        buildHeap(top, 0, top.length);// 构建最小堆, top[0]为最小元素  
        for (i = topnum; i < number; i++) {  
  
            int currentNumber2 = Math.abs(random.nextInt(maxnum));//设置为随机数  

            // 大于 top[0]则交换currentNumber2  重构最小堆  
            if (top[0] < currentNumber2) {  
                top[0] = currentNumber2;  
                shift(top, 0, top.length, 0); // 构建最小堆 top[0]为最小元素  
            }  
        }  
        System.out.println(Arrays.toString(top));  
        sort(top);  
        System.out.println("==============================");
        System.out.println(Arrays.toString(top));  
          
        Date endTime = new Date();  
        System.out.println("用了"+(endTime.getTime() - startTime.getTime())+"毫秒");  
   
    }  
      
     
   
    //构建最小堆  
    public static void buildHeap(int[] array, int from, int len) {  
        int pos = (len - 1) / 2;  
        for (int i = pos; i >= 0; i--) {  
            shift(array, from, len, i);  
        }  
    }  
   
    /** 
     * @param array top数组 
     * @param from 开始 
     * @param len 数组长度 
     * @param pos 当前节点index 
     * */  
     //调整堆,使成为最小堆
    public static void shift(int[] array, int from, int len, int pos) {  
        // 保存该节点的值   
        int tmp = array[from + pos];  
  
        int index = pos * 2 + 1;// 得到当前pos节点的左节点  
        while (index < len)//  存在左节点  
        {  
            if (index + 1 < len  
                    && array[from + index] > array[from + index + 1])// 如果存在右节点  
            {  
                // 如果右边节点比左边节点小,就和右边的比较  
                index += 1;  
            }  
               
            if (tmp > array[from + index]) {  
                array[from + pos] = array[from + index];  
                pos = index;  
                index = pos * 2 + 1;  
            } else {  
                break;  
            }  
        }  
        // 最终全部置换完毕后 ,把临时变量赋给最后的节点  
        array[from + pos] = tmp;  
    }  

    public static void swap(int array[],int i, int j) {  
        int temp = array[i];  
        array[i] = array[j];  
        array[j] = temp;  
    }  

      
    public static void sort(int[] array){
        for (int i = array.length-1; i > 0; i--) {  
            /*把根节点跟最后一个元素交换位置,调整剩下的节点,即可排好序*/  
            swap(array,0, i);  
            shift(array,0, i - 1,0);  
        }  

       
    }  
  
}  


源码下载:

堆排序的应用:从1亿条数据中从大到小取前10000条

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
相信很多喜欢研究网页界面的童鞋都遇到过一个奇妙的现象:网页中很多图片素材被合成在一张图片上。
通过部署和使用大数据分析工具,分析流程可以帮助公司提高运营效率,产生新的利润,获得竞争优势。
  作为互联网金融当中最热门最活跃的领域,P2P现在发展速度非常快。P2P模式最早诞生于英美,它的
大数据(big data),大在哪里,它和传统数据又有何区别,在教育领域有何应用? 大数据:也称巨量资料
相信很多喜欢研究网页界面的童鞋都遇到过一个奇妙的现象:网页中很多图片素材被合成在一张图片上。
相信很多喜欢研究网页界面的童鞋都遇到过一个奇妙的现象:网页中很多图片素材被合成在一张图片上。
相信很多喜欢研究网页界面的童鞋都遇到过一个奇妙的现象:网页中很多图片素材被合成在一张图片上。
导弹工厂到摩托车间:制造业如何应用大数据 本文来源于:腾讯科技  发表于:2013-05-17 09:26:17
  腾讯公司从2012年开始,通过对服务器运营流程、工具系统的建设,服务器从一线到三线的运营基本
大数据的处理 经过长时间的实践和总结,我们发现服务器运营的大数据有以下四个特点,由浅入深,分别
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号