疯狂的Java算法——插入排序,归并排序以及并行归并排序.docx

从古至今的难题在 IT 届有一道百算不厌其烦的题, 俗称排序。不管是你参加 BAT 等高端笔试, 亦或是藏匿于街头小巷的草根笔试,都会经常见到这样一道百年难得一解的问题。今天 LZ 有幸与各位分享一下算法届的草根明星, 排序届的领衔大神——插入排序以及归并排序。最后,在头脑风暴下, LZ 又有幸认识了一位新朋友,名叫并行归并排序。接下来,咱们就一一认识一下,并且在最后来一次“算林大会”吧。插入排序简介插入排序, 算林称最亲民的排序算法, 插入排序采用最简单的插入方式对一个整数数组进行排序。它循环数组中从第二个开始的所有元素, 并且将每一个循环到的元素插入到相应的位置,从而实现排序的目的。插入排序的代码展示使用 Java 代码描述插入排序,可以用以下的代码。 package algorithm; /** * ***@author zuoxiaolong * */ public abstract class InsertSort { public static void sort( int [] numbers){ for ( int i= 1;i< ; i++) { int currentNumber = numbers[i]; int j=i- 1; while (j >=0 && numbers[j] > currentNumber) { numbers[j + 1]= numbers[j]; j--; } numbers[j + 1]= currentNumber; }}} 这个算法从数组的第二个元素开始循环, 将选中的元素与之前的元素一一比较, 如果选中的元素小于之前的元素,则将之前的元素后移,最后再将选中的元素放在合适的位置。在这个算法执行的过程中,总是保持着索引 i 之前的数组是升序排列的。插入排序理解起来比较简单, 因此 LZ 就不过多的解释它的实现原理了, 尚未理解的猿友可以自行研究。插入排序的性能分析接下来, 咱们来简单分析一下插入排序的性能。首先, 插入排序当中有两个循环, 假设数组的大小为 n ,则第一个循环是 n-1 次,第二个 while 循环在最坏的情况下是 1到n- 1 次。因此插入排序的时间复杂度大约为如下形式。 1+2+3+4+... +n-1=n(n-1)/2=O(n 2) 时间复杂度为输入规模的 2 次函数,可见插入排序的时间复杂度是比较高的。这是原理上的简单分析, 最后在“算林大会”中, 各位可以清楚的看到插入排序随着输入规模的增长,时间会指数倍的上升。归并排序简介归并排序, 算林届的新秀, 引领着分治法的潮流。归并排序将排序问题拆分, 比如分成两个较小的数组, 然后对拆分后的数组分别进行排序, 最后再将排序后的较小数组进行合并。这种思想是一种算法设计的思想, 很多问题都可以采用这种方式解决。映射到编程领域, 其实就是递归的思想。因此在归并排序的算法中,将会出现递归调用。归并排序的代码展示归并排序主要由两个方法组成, 一个是用于合并两个已经排序的数组的方法, 一个则是递归方法,用于将问题无限拆分。接下来咱们一起看看归并排序的 Java 代码展示,如下所示。 package algorithm; /** * ***@author zuoxiaolong * */ public abstract class MergeSort { public static void sort( int [] numbers){ sort(numbers, 0, ); } public static void sort( int [] numbers, int pos, int end){ if ((end - pos) > 1){ int offset = (end + pos) / 2; sort(numbers, pos, offset); sort(numbers, offset, end); merge(numbers, pos, offset, end); } } public static void merge( int [] numbers, int pos, int offset, int end){ int [] array1 = new int [offset - pos]; int [] array2 = new int [end - offset]; (numbers, pos, array1, 0, ); (numbers, offset, array2, 0, ); for ( int i= pos,j=0,k=0; i<