package com.suanfa;

public class QuickSort {

    /**
     * 快速排序的实现
     * @param args
     */
    
        //用于快速排序的子数组的排序
     public   static int partition (int [] array, int front, int tail){
        
         int middle;  //用于保存中间位置
        int pivot;   //保存枢轴的位置
        int boundary;  //保存边界位置
        int temp ;     //用于保存临时值，用于值交换
        
        middle =(front + tail)/2; //获取中间值
        
        //1.用于将枢轴与子数组的做后一个数据项交换
        pivot = array[middle];
        array[middle] = array[tail];
        array[tail] = pivot;
        
        //2.设置边界，在数组的前面
        boundary = front;
        
        //3.遍历子数组，
        for( int i = front; i<tail; i++){
            
            if(array[i]<pivot){
                
                
        //4.如果当前元素小于枢轴，则将该元素和边界交换，并将交换后的边界往后移动一位
                temp = array[boundary];
                array[boundary] = array[i];
                array[i] = temp;
                
                boundary++;
            }
        }
        //最后把边界和子数组的最后一个元素交换
        temp = array[tail];
        array[tail]  = array[boundary];
        array[boundary] = temp;
        
        return boundary;
    }
     
        
    public static void quickSort(int [] array, int front, int tail){
    
        if(front<tail){
            
            int pivotPosition = partition(array, front ,tail);
            //使用递归实现子数组的划分，每次根据不同的边界来划分
            // 划分左数组
            quickSort(array, front, pivotPosition-1);
            //划分右数组
            quickSort(array, pivotPosition+1, tail);
            
        }
    }
}

------解决方案--------------------

如果文件记录建了索引（如B+索引），获取TOPN条数据是很简单的事。
在没有索引的情况下，一般的做法是通过容量固定的最大堆或最小堆筛选出TOPN条数据。

------解决方案--------------------

分次读啊 
每次读100万条   留下最大的1万条
清缓存    可是JAVA不能人为主动释放内存
在读下100万条   再留下最大的1万条
如此反复

------解决方案--------------------

这种大数据量的东西，基本上都是用分布式的方法来实现的。

两个步骤： 分治 、 归并

先将这3亿的数据分给 n台机器，每台机器处理3亿/n个，找到其中的前1万。

两两机器归并，最终找出最终解。

这其中一个manager computer负责分治和归并的逻辑。