《算法导论》学习之关于如何利用排序算法，从1亿个数中，选出最大（小）的100个数

本文主要是介绍《算法导论》学习之关于如何利用排序算法，从1亿个数中，选出最大（小）的100个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先声明：本文内容是参考别人的博客，链接为：http://blog.csdn.net/beiyeqingteng/article/details/7534489

前言：

刚刚在CSDN上看到一个网友利用最小堆实现 “ 获取一亿数据获取前100个最大值” 。原帖请看：http://blog.csdn.net/yjflinchong/article/details/7533972。然后自己利用quicksort的原理也写了一个程序来解决那个问题。通过测试，基于quicksort原理的方法平均运行时间是1.264秒，基于最小堆方法的平均运行时间是0.288秒 (网友写的程序运行时间比我的大很多，0.288秒这个程序是我自己写的，如果测试网友写的基于minHeap的方法，运行时间是2.501秒)。基于最小堆方法运行时间很稳定（每次运行时间相差很小），基于quicksort原理的方法运行时间不稳定（每次运行时间相差大）。

基于quicksort实现的原理如下：

1. 假设数组为 array[N] (N = 1 亿)，首先利用quicksort的原理把array分成两个部分，左边部分比 array[N - 1] (array中的最后一个值，即pivot) 大，右边部分比pivot 小。然后，可以得到 array[array.length - 1] (即 pivot) 在整个数组中的位置，假设是 k.
2. 如果 k 比 99 大，我们在数组[0, k - 1]里找前 100 最大值。（继续递归）
3. 如果 k 比 99 小，我们在数组[k + 1, ..., N ]里找前 100 - (k + 1) 最大值。（继续递归）
4. 如果 k == 99, 那么数组的前 100 个值一定是最大的。（退出）

代码如下：

[java]  view plain copy  
 
 public class TopHundredQuickSort {  
       
     public void tophundred(int[] array, int start, int end, int k) {  
           
         int switchPointer = start;  
         int pivot = array[end]; //array最后一个值作为pivot  
         for (int i = start; i < end; i++) {  
             if (array[i] >= pivot) {  
                 swap(array, switchPointer, i);  
                 switchPointer++;  
             }  
         }  
         swap(array, end, switchPointer);//交换后，array左边的值比pivot大，右边的值比pivot小  
           
         if (switchPointer < k - 1) {  
             tophundred(array, switchPointer + 1, end, k);  
         } else if (switchPointer == k - 1) {  
             return;  
         } else {  
             tophundred(array, 0, switchPointer - 1, k);  
         }  
     }  
       
     public void swap(int[] array, int i, int j) {  
         int temp = array[i];  
         array[i] = array[j];  
         array[j] = temp;          
     }  
       
     public static void main(String[] args) {  
           
         // the size of the array  
         int number = 100000000;  
         // the top k values  
         int k = 100;  
         // the range of the values in the array  
         int range = 1000000001;  
   
         //input for minHeap based method  
         int[] array = new int[number];  
           
         Random random = new Random();  
         for (int i = 0; i < number; i++) {  
             array[i] = random.nextInt(range);  
         }  
           
         TopHundredQuickSort topHundred = new TopHundredQuickSort();  
           
         //start time  
         long t1 = System.currentTimeMillis();   
         topHundred.tophundred(array, 0, array.length - 1, k);  
         //end time  
         long t2 = System.currentTimeMillis();   
           
         System.out.println("The total execution time " +  
                 "of quicksort based method is " + (t2 - t1) +" millisecond!");  
           
         // print out the top k largest values in the top array  
         System.out.println("The top "+ k + "largest values are:");  
         for (int i = 0; i < k; i++) {  
             System.out.println(array[i]);  
         }  
                   
     }  
 }  

下面是基于minHeap写的程序。如果你懂heap sort，那么下面的程序很容易理解。

[java]  view plain copy  
 
 public class TopHundredHeap {  
       
     public static void main(String[] args) {  
         // the size of the array  
         int number = 100000000;  
         // the top k values  
         int k = 100;  
         // the range of the values in the array  
         int range = 1000000001;  
   
         //input for minHeap based method  
         int[] array = new int[number];  
           
         Random random = new Random();  
         for (int i = 0; i < number; i++) {  
             array[i] = random.nextInt(range);  
         }  
           
         TopHundredHeap thh = new TopHundredHeap();  
           
         long t1, t2;  
         //start time  
         t1 = System.currentTimeMillis();   
         int[] top = thh.topHundred(array, k);  
           
         //end time  
         t2 = System.currentTimeMillis();   
         System.out.println("The total execution time of " +  
                 "quicksort based method is " + (t2 - t1) +" millisecond!");  
           
         // print out the top k largest values in the top array  
         System.out.println("The top "+ k + "largest values are:");  
         for (int i = 0; i < k; i++) {  
             System.out.println(top[i]);  
         }  
     }  
       
     public int[] topHundred(int[] array, int k) {  
         // the heap with size k  
         int[] top = new int[k];  
           
         for (int i = 0; i < k; i++) {  
             top[i] = array[i];  
         }  
           
         buildMinHeap(top);  
           
         for (int i = k; i < array.length; i++) {  
             if (top[0] < array[i]) {  
                 top[0] = array[i];  
                 minHeapify(top, 0, top.length);  
             }  
         }  
           
         return top;  
     }  
       
     // create a min heap  
     public void buildMinHeap(int[] array) {  
         int heapSize = array.length;  
         for (int i = array.length / 2 - 1; i >= 0; i--) {  
             minHeapify(array, i, heapSize);  
         }  
     }  
       
      /// MinHeapify is to build the min heap from the 'position'  
     public void minHeapify(int[] array, int position, int heapSize)  
     {  
         int left = left(position);  
         int right = right(position);  
         int maxPosition = position;  
           
         if (left < heapSize && array[left] < array[position]) {  
             maxPosition = left;  
         }  
           
         if (right < heapSize && array[right] < array[maxPosition]) {  
             maxPosition = right;  
         }  
           
         if (position != maxPosition) {  
             swap(array, position, maxPosition);  
             minHeapify(array, maxPosition, heapSize);  
         }  
     }  
       
     public void swap(int[] array, int i, int j) {  
         int temp = array[i];  
         array[i] = array[j];  
         array[j] = temp;          
     }  
       
     /// return the left child position  
     public int left(int i)  
     {  
         return 2 * i + 1;  
     }  
     /// return the right child position  
     public int right(int i)  
     {  
         return 2 * i + 2;  
     }   
 }  