归并排序
作者:
超人不会飞_5
,
2024-11-29 15:40:45
,
所有人可见
,
阅读 3
import java.util.Scanner;
public class Main{
static int[] temp = new int[100010];
static void mergeSort(int q[] ,int l,int r){
if(l==r) return;
//确定分界点,归并排序的分界点和快排的分界点代表的含义不同
int mid = (l+r)/2;
//递归排序左右区间
mergeSort(q,l,mid);
mergeSort(q,mid+1,r);
int k = 0,i = l,j = mid+1;
while(i <= mid && j <= r){
if(q[i] <= q[j]){
temp[k++] = q[i++];
}else{
temp[k++] = q[j++];
}
}
//排序剩余数组中的元素
while(i <= mid) temp[k++] = q[i++];
while(j <= r) temp[k++] = q[j++];
//把排序好的temp数组赋值给原数组
for(i=l,j=0;i<=r;i++,j++) q[i] = temp[j];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] q = new int[n];
for(int i = 0; i <= n-1; i++){
q[i] = sc.nextInt();
}
mergeSort(q,0,n-1);
for(int i = 0;i <= n-1; i++){
System.out.print(q[i]+" ");
}
}
}