题目描述
给定你一个长度为 n的整数数列。请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n个整数(所有整数均在 1∼109范围内),表示整个数列。
输出格式
输出共一行,包含 n个整数,表示排好序的数列。
数据范围
1≤n≤100000
java 代码
impor java.util.Scanner
public class Main{
static final int N=100010;
static int[] q=new int[N];
static int tmp=new int[N];
public static void main(String[] args)
{
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
for(int i=0;i<n;i++)
{
q[i]=scanner.nextInt();
}
merge_sort(q,0,n-1);
for(int i=0;i<n;i++)
{
System.out.println(q[i]+" ");
}
}
public static void merge_sort(int[] q,int l,int r)
{
if(l>=r) return;
int mid=(l+r)>>1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int k=1,i=l,j=mid+1;
while(i<mid && j<=r)
{
if(q[i]<q[j]) tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(int p=l,m=1;p<=r;p++,m++)
{
q[p]=tmp[m];
}
}
}
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
模拟过程
当程序运行时,它首先会读取输入,第一个数字表示接下来要输入的数字的数量,然后读取这些数字,并将它们存储在数组 q 中。
对于输入样例 5 3 1 2 4 5,程序的运行会按照以下步骤进行:
读取第一个数字 5,表示接下来有五个数字要输入。
读取这五个数字 3 1 2 4 5 并存储在数组 q 中。
调用 mergeSort(q, 0, 4),表示对数组 q 的从索引 0 到索引 4 的元素进行归并排序。
归并排序的过程如下:
mergeSort(q, 0, 4):
计算中间位置 mid = (0 + 4) / 2 = 2。
调用 mergeSort(q, 0, 2),对左半部分数组 [3, 1, 2] 进行排序。
调用 mergeSort(q, 3, 4),对右半部分数组 [4, 5] 进行排序。
mergeSort(q, 0, 2):
计算中间位置 mid = (0 + 2) / 2 = 1。
调用 mergeSort(q, 0, 1),对左半部分数组 [3, 1] 进行排序。
调用 mergeSort(q, 2, 2),对右半部分数组 [2] 进行排序。
mergeSort(q, 0, 1):
计算中间位置 mid = (0 + 1) / 2 = 0。
调用 mergeSort(q, 0, 0),对左半部分数组 [3] 进行排序。
调用 mergeSort(q, 1, 1),对右半部分数组 [1] 进行排序。
递归到最底层,单个元素无需排序。
接下来,对 [3] 和 [1] 进行合并,得到 [1, 3]。
回到 mergeSort(q, 2, 2),单个元素无需排序。
接着,对 [1, 3] 和 [2] 进行合并,得到 [1, 2, 3]。
回到 mergeSort(q, 3, 4),单个元素无需排序。
接着,对 [4] 和 [5] 进行合并,得到 [4, 5]。
最后,对 [1, 2, 3] 和 [4, 5] 进行合并,得到最终排序结果 [1, 2, 3, 4, 5]。
程序最终输出排序后的数组元素为 1 2 3 4 5。