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

编程入门 行业动态 更新时间:2024-10-07 04:35:28

疯狂的Java<a href=https://www.elefans.com/category/jswz/34/1770096.html style=算法——插入排序,归并排序以及并行归并排序"/>

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

从古至今的难题

  

  在IT届有一道百算不厌其烦的题,俗称排序。不管是你参加BAT等高端笔试,亦或是藏匿于街头小巷的草根笔试,都会经常见到这样一道百年难得一解的问题。

  今天LZ有幸与各位分享一下算法届的草根明星,排序届的领衔大神——插入排序以及归并排序。最后,在头脑风暴下,LZ又有幸认识了一位新朋友,名叫并行归并排序。接下来,咱们就一一认识一下,并且在最后来一次“算林大会”吧。

 

插入排序简介

  

  插入排序,算林称最亲民的排序算法,插入排序采用最简单的插入方式对一个整数数组进行排序。它循环数组中从第二个开始的所有元素,并且将每一个循环到的元素插入到相应的位置,从而实现排序的目的。

  

插入排序的代码展示

  

  使用Java代码描述插入排序,可以用以下的代码。

package algorithm;/*** @author zuoxiaolong**/
public abstract class InsertSort {public static void sort(int[] numbers){for (int i = 1; i < numbers.length; 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(n2

  时间复杂度为输入规模的2次函数,可见插入排序的时间复杂度是比较高的。这是原理上的简单分析,最后在“算林大会”中,各位可以清楚的看到插入排序随着输入规模的增长,时间会指数倍的上升。

  

归并排序简介

  

  归并排序,算林届的新秀,引领着分治法的潮流。归并排序将排序问题拆分,比如分成两个较小的数组,然后对拆分后的数组分别进行排序,最后再将排序后的较小数组进行合并。

  这种思想是一种算法设计的思想,很多问题都可以采用这种方式解决。映射到编程领域,其实就是递归的思想。因此在归并排序的算法中,将会出现递归调用。

  

归并排序的代码展示

  

  归并排序主要由两个方法组成,一个是用于合并两个已经排序的数组的方法,一个则是递归方法,用于将问题无限拆分。接下来咱们一起看看归并排序的Java代码展示,如下所示。

package algorithm;/*** @author zuoxiaolong**/
public abstract class MergeSort {public static void sort(int[] numbers){sort(numbers, 0, numbers.length);}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[

更多推荐

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

本文发布于:2024-03-12 14:27:44,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1731715.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:算法   疯狂   Java

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!