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

2024-05-16 00:18

本文主要是介绍《算法导论》学习之关于如何利用排序算法,从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
  1. public class TopHundredQuickSort {  
  2.       
  3.     public void tophundred(int[] array, int start, int end, int k) {  
  4.           
  5.         int switchPointer = start;  
  6.         int pivot = array[end]; //array最后一个值作为pivot  
  7.         for (int i = start; i < end; i++) {  
  8.             if (array[i] >= pivot) {  
  9.                 swap(array, switchPointer, i);  
  10.                 switchPointer++;  
  11.             }  
  12.         }  
  13.         swap(array, end, switchPointer);//交换后,array左边的值比pivot大,右边的值比pivot小  
  14.           
  15.         if (switchPointer < k - 1) {  
  16.             tophundred(array, switchPointer + 1, end, k);  
  17.         } else if (switchPointer == k - 1) {  
  18.             return;  
  19.         } else {  
  20.             tophundred(array, 0, switchPointer - 1, k);  
  21.         }  
  22.     }  
  23.       
  24.     public void swap(int[] array, int i, int j) {  
  25.         int temp = array[i];  
  26.         array[i] = array[j];  
  27.         array[j] = temp;          
  28.     }  
  29.       
  30.     public static void main(String[] args) {  
  31.           
  32.         // the size of the array  
  33.         int number = 100000000;  
  34.         // the top k values  
  35.         int k = 100;  
  36.         // the range of the values in the array  
  37.         int range = 1000000001;  
  38.   
  39.         //input for minHeap based method  
  40.         int[] array = new int[number];  
  41.           
  42.         Random random = new Random();  
  43.         for (int i = 0; i < number; i++) {  
  44.             array[i] = random.nextInt(range);  
  45.         }  
  46.           
  47.         TopHundredQuickSort topHundred = new TopHundredQuickSort();  
  48.           
  49.         //start time  
  50.         long t1 = System.currentTimeMillis();   
  51.         topHundred.tophundred(array, 0, array.length - 1, k);  
  52.         //end time  
  53.         long t2 = System.currentTimeMillis();   
  54.           
  55.         System.out.println("The total execution time " +  
  56.                 "of quicksort based method is " + (t2 - t1) +" millisecond!");  
  57.           
  58.         // print out the top k largest values in the top array  
  59.         System.out.println("The top "+ k + "largest values are:");  
  60.         for (int i = 0; i < k; i++) {  
  61.             System.out.println(array[i]);  
  62.         }  
  63.                   
  64.     }  
  65. }  

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

[java]  view plain copy
  1. public class TopHundredHeap {  
  2.       
  3.     public static void main(String[] args) {  
  4.         // the size of the array  
  5.         int number = 100000000;  
  6.         // the top k values  
  7.         int k = 100;  
  8.         // the range of the values in the array  
  9.         int range = 1000000001;  
  10.   
  11.         //input for minHeap based method  
  12.         int[] array = new int[number];  
  13.           
  14.         Random random = new Random();  
  15.         for (int i = 0; i < number; i++) {  
  16.             array[i] = random.nextInt(range);  
  17.         }  
  18.           
  19.         TopHundredHeap thh = new TopHundredHeap();  
  20.           
  21.         long t1, t2;  
  22.         //start time  
  23.         t1 = System.currentTimeMillis();   
  24.         int[] top = thh.topHundred(array, k);  
  25.           
  26.         //end time  
  27.         t2 = System.currentTimeMillis();   
  28.         System.out.println("The total execution time of " +  
  29.                 "quicksort based method is " + (t2 - t1) +" millisecond!");  
  30.           
  31.         // print out the top k largest values in the top array  
  32.         System.out.println("The top "+ k + "largest values are:");  
  33.         for (int i = 0; i < k; i++) {  
  34.             System.out.println(top[i]);  
  35.         }  
  36.     }  
  37.       
  38.     public int[] topHundred(int[] array, int k) {  
  39.         // the heap with size k  
  40.         int[] top = new int[k];  
  41.           
  42.         for (int i = 0; i < k; i++) {  
  43.             top[i] = array[i];  
  44.         }  
  45.           
  46.         buildMinHeap(top);  
  47.           
  48.         for (int i = k; i < array.length; i++) {  
  49.             if (top[0] < array[i]) {  
  50.                 top[0] = array[i];  
  51.                 minHeapify(top, 0, top.length);  
  52.             }  
  53.         }  
  54.           
  55.         return top;  
  56.     }  
  57.       
  58.     // create a min heap  
  59.     public void buildMinHeap(int[] array) {  
  60.         int heapSize = array.length;  
  61.         for (int i = array.length / 2 - 1; i >= 0; i--) {  
  62.             minHeapify(array, i, heapSize);  
  63.         }  
  64.     }  
  65.       
  66.      /// MinHeapify is to build the min heap from the 'position'  
  67.     public void minHeapify(int[] array, int position, int heapSize)  
  68.     {  
  69.         int left = left(position);  
  70.         int right = right(position);  
  71.         int maxPosition = position;  
  72.           
  73.         if (left < heapSize && array[left] < array[position]) {  
  74.             maxPosition = left;  
  75.         }  
  76.           
  77.         if (right < heapSize && array[right] < array[maxPosition]) {  
  78.             maxPosition = right;  
  79.         }  
  80.           
  81.         if (position != maxPosition) {  
  82.             swap(array, position, maxPosition);  
  83.             minHeapify(array, maxPosition, heapSize);  
  84.         }  
  85.     }  
  86.       
  87.     public void swap(int[] array, int i, int j) {  
  88.         int temp = array[i];  
  89.         array[i] = array[j];  
  90.         array[j] = temp;          
  91.     }  
  92.       
  93.     /// return the left child position  
  94.     public int left(int i)  
  95.     {  
  96.         return 2 * i + 1;  
  97.     }  
  98.     /// return the right child position  
  99.     public int right(int i)  
  100.     {  
  101.         return 2 * i + 2;  
  102.     }   
  103. }  
时间复杂度分析:

基于minheap方法 的时间复杂度是 O(lg K * N), 基于quicksort 方法的平均时间复杂度是 O(N),但是最差是O(N^2). 这也是为何基于quicksort 方法它的时间不稳定的原因。


这篇关于《算法导论》学习之关于如何利用排序算法,从1亿个数中,选出最大(小)的100个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/993329

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

重新对Java的类加载器的学习方式

《重新对Java的类加载器的学习方式》:本文主要介绍重新对Java的类加载器的学习方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍1.1、简介1.2、符号引用和直接引用1、符号引用2、直接引用3、符号转直接的过程2、加载流程3、类加载的分类3.1、显示

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen