题目描述
给定你一个长度为 n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。并排好序的数列按顺序输出。
输入格式:
输入共两行,第一行包含整数 n。
第二行包含 n个整数(所有整数均在 1∼10^9范围内),表示整个数列。
输出格式:
输出共一行,包含 n个整数,表示排好序的数列。
数据范围:
1≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
//787. 归并排序
//思路 1.确定分界点mid mid=(l+r)/2
// 2.递归排序left right
// 3.归并,合二为一
// 比较左右两个序列的第一个值哪个小,小的那个为最小值(因为左右序列都已按照从小到大排序)
// 假设为序列1,序列2,若序列1第一个值最小,就将序列1的指针往后移1位,与序列2指针的值(即第1位)进行比较,
// 每次比较都把得到的值放入一个数组中,依此类推直到有一个序列的指针走到终点,将另一个序列剩余的部分放入数组的最后
/*
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
static int tmp[];
public static void main(String[] args) throws IOException {
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
int n= Integer.parseInt(bf.readLine());
int[] arr=new int[n];
String[] res=bf.readLine().split(" ");
for(int i=0;i<n;i++){
arr[i]=Integer.parseInt(res[i]);
}
mergeSort(arr,0,n-1);
for(int i=0;i<n;i++){
System.out.print(arr[i]+" ");
}
}
public static void mergeSort(int[] m,int l,int r){//l指数组最左端的索引,r指数组最右端的索引
if(l>=r){
return;
}
int mid=(l+r)/2;//取中间值
////递归处理子问题
mergeSort(m,l,mid);
mergeSort(m,mid+1,r);
tmp=new int [r-l+1];//定义一个数组,用于存放得到的数
int k=0;
int i=l;
int j=mid+1;
while (i<=mid&&j<=r ){
if(m[i]<=m[j]){
/* tmp[k]=m[i];
k++;
i++; */
tmp[k++]=m[i++];
}else{
tmp[k++]=m[j++];
}
}
while(i<=mid){//左半边没有循环完,右半边已经遍历完
tmp[k++]=m[i++];//将左半边剩余的数都放入tmp的后面
}
while(j<=r){//右半边没有循环完,左半边已经遍历完
tmp[k++]=m[j++];//将右半边剩余的数都放入tmp的后面
}
for(i=l,j=0;i<=r;i++,j++){//将tmp里的值复制到m里去
m[i]=tmp[j];
}
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla