归并排序流程图（AcWing 787.归并排序（Java））

题目来源：https://www.acwing.com/problem/content/description/789/

题目描述

给定你一个长度为 n 的整数数列    
    
    
。

请你使用归并排序对这个数列按照从小到大进行排序  


     


     


    。

并将排好序的数列按顺序输出


 




 




 


。

输入格式

输入共两行    
    
    
，第一行包含整数 n   

   

   

。

第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内）  


     


     


    ，表示整个数列   

     

     

   。

输出格式

输出共一行


 




 




 


，包含 n 个整数   

   

   

，表示排好序的数列



  




  




  

。

数据范围

1≤n≤1000001≤n≤100000

输入样例： 5 3 1 2 4 5 输出样例： 1 2 3 4 5

思路讲解

首先确定中间基准点mid = left + （right - left） / 2   

     

     

   ，在每次进行方法时先进性一次递推进行数组的分割



  




  




  

，将数组分为单个值后进行排序  


  


  


，在对每个小数组及进行归并    
     
     
  ，最后归并为一个排好序的数组 那么如何进行排序呢？我们应当确定的是




   




   




   
，先经过递推后的输皆为单个数 



 



 



，那么二者进行比较后将该数存入临时数组中即可  


  


  


。这样我们就得到了两两成对的数组    
     
     
  。然后我们再进行判断                ，例如数组a1,a2,b1,b2




    




    




    ，首先我们应确定的是a1<a2,b数组同理




   




   




   
。那么我们便要将两个数组中较小的值















，也就是靠前的值进行比较               ，然后再接着比··· ···直到整个数组合并完成 



 



 



。 需要注意的是 



     



     



     ，为了防止某一段数组的长度大于另一端















，需加入判断语句    
    
    
，将剩下的值一起存入临时数组（因为剩下的值也是排序好的  


     


     


    ，直接加进去就好）

代码

import java.util.Scanner; public class Main { //开辟足够大的数组空间 static int N = 100010; static int[] q = new int[N], temp = new int[N]; public static void main(String[] args) { //输入数组大小以及数组的值 Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { q[i] = sc.nextInt(); } //进行排序 merge_sort(q,0,n-1); //输出结果 for(int i = 0; i < n; i ++) System.out.print(q[i] + " "); } public static void merge_sort(int []q,int left,int right) { //进行判断 if (left >= right) return; //进行递归


 




 




 


，将数组分为最小单位的值,接着在从最小进行排序   

   

   

，逐渐到整个数组 int mid = left + (right - left) / 2; merge_sort(q, left, mid); merge_sort(q, mid + 1, right); int i = left, j = mid + 1;//建立双指针   

     

     

   ，i指向前一个数



  




  




  

，j指向后一个数 int k = 0;//令temp从0开始  


  


  


，往其中添加元素 //进行归并操作    
     
     
  ，将数存放至临时数组temp while (i <= mid && j <= right) {//确认边界 if (q[i] <= q[j]) temp[k++] = q[i++]; else temp[k++] = q[j++]; } //防止i或j提前用光的情况发生 while (i <= mid) temp[k++] = q[i++]; while (j <= right) temp[k++] = q[j++]; for(i = left, k = 0; i <= right; i ++, k ++) q[i] = temp[k];//把原数组未排序的部分覆盖成已排序部分 } }

个人失误

while (i <= mid && j <= right) {//确认边界 if (q[i] <= q[j]) temp[k++] = q[i++]; else temp[k++] = q[j++]; }

在这里我将if-else中的temp[k++] = q[i++]与temp[k++] = q[j++]中的q全部失误写成了temp




   




   




   
，直接导致结果中出现了不该存在的“0    
    
    
” 



 



 



，查了好几遍才发现······