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

思路讲解

  1. 首先确定中间基准点mid = left + （right - left） / 2，在每次进行方法时先进性一次递推进行数组的分割，将数组分为单个值后进行排序，在对每个小数组及进行归并，最后归并为一个排好序的数组
  2. 那么如何进行排序呢？我们应当确定的是，先经过递推后的输皆为单个数，那么二者进行比较后将该数存入临时数组中即可。这样我们就得到了两两成对的数组。然后我们再进行判断，例如数组a1,a2,b1,b2，首先我们应确定的是a1<a2,b数组同理。那么我们便要将两个数组中较小的值，也就是靠前的值进行比较，然后再接着比··· ···直到整个数组合并完成。
  3. 需要注意的是，为了防止某一段数组的长度大于另一端，需加入判断语句，将剩下的值一起存入临时数组（因为剩下的值也是排序好的，直接加进去就好）

代码

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”，查了好几遍才发现······

标签 , ,

发表回复