java实现归并排序算法

今天药忘吃喽~ 2022-05-09 00:28 356阅读 0赞

前面我们讲了归并排序算法，接下来我们来用java代码实现呗，如下

  1. package ttt;
  3. import java.util.Arrays;
  5. public class MergeSort {
  6.     public static int[] lastMergeSort(int[] list1,int[] list2) {
  7.         int i = 0, j = 0, k = 0;
  8.         int [] temp = new int[list1.length + list2.length];
  9.         while (i < list1.length && j < list2.length) {
  10.             if (list1[i] <= list2[j]) {
  11.                 temp[k++] = list1[i++];
  12.             }else {
  13.                 temp[k++] = list2[j++];
  14.             }
  15.         }
  17.         if (i == list1.length) {
  18.             while(j <list2.length) {
  19.                 temp[k++] = list2[j++];
  20.             }
  21.         }
  22.         if (j == list2.length) {
  23.             for(;i <list1.length;)
  24.                 temp[k++] = list1[i++];            
  25.         }
  26.         return temp;
  27.     }
  29.     public static int[] mergeSort(int[] theArray) {
  30.         if(theArray.length ==1) {
  31.             return theArray;
  32.         }
  33.         int mid = (int)theArray.length/2;
  34.         int[] leftArray = mergeSort(Arrays.copyOfRange(theArray, 0, mid));//前闭后开区间，这种写法开闭了很多空间，有点浪费，实则可以通过别的写法避免的
  35.         int[] rightArray = mergeSort(Arrays.copyOfRange(theArray, mid, theArray.length));
  36.         return lastMergeSort(leftArray, rightArray);
  37.     }
  39.     public static void main(String[] args) {
  40.         int []theArray = {10,1,18,30,23,12,7,5,18,17};
  41.         System.out.print("之前的排序：");
  42.         for(int i = 0; i < theArray.length; i++) {
  43.             System.out.print(theArray[i] + " ");
  44.         }
  45.         int [] larray = {1,4,10};
  46.         int [] rarray = {2,6,8,11,15,18};
  47. //        int []result_array = lastMergeSort(larray,rarray);
  48.         int []resultArray = mergeSort(theArray);
  49.         System.out.print("归并排序：");
  50.         for(int v : resultArray) {
  51.             System.out.print(v + " ");
  52.         }
  53.     }
  54. }

运行结果如下

  1. 之前的排序：10 1 18 30 23 12 7 5 18 17 归并排序：1 5 7 10 12 17 18 18 23 30

符合预期

发表评论

表情：
评论列表 （有 0 条评论，356人围观）

还没有评论，来说两句吧...

相关阅读

    相关 JAVA_算法_归并排序

    思想： 把一个大的数组细分成两个不同的数组， 循环这个过程。直到数组中的元素只有1或0个元素。 当数组中的只有两个元素时，比较两个元素的大小，前一个大于后一个就交换。 然

    布满荆棘的人生布满荆棘的人生/ 0 赞/ 196 阅读

    相关 归并排序算法（Java实现）

    1、基本思想 归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列

    向右看齐向右看齐/ 0 赞/ 328 阅读

    相关 归并排序算法——java

    什么是归并排序算法？ 答：归并排序算法就是利用分治思想将数组分成两个小组A，B，再将A，B小组各自分成两个小组，依次类推，直到分出来的小组只有一个数据时，可以认为这个小组已经

    迷南。迷南。/ 0 赞/ 242 阅读

    相关 排序算法之归并排序（Java实现）

    归并排序的思想是将局部有序的数组合并为一个大的有序数组，前提是需要保证局部数组有序，如果局部没有顺序，那么就拆分，再合并，最差的情况是，拆到两个数组都只有一个元素的时候，这时候

    Dear 丶Dear 丶/ 0 赞/ 364 阅读