1- 归并排序原理
1-1 主要思想
归并排序基于分治
-
- 将序列中待排序的数数字分为若干组,每个数字分为一组
-
- 将若干组两两合并,保证合并后的数组是有序的
-
- 重复第二步操作直到只剩下一组,排序完成
时间复杂度:
- 平均时间复杂度:
O(nlogn)
稳定性
- 归并排序是稳定的
1-2 实现步骤
- ① 确定分界点
- 以整个数组的中间部分为分界点,分割
mid = (l+r)/2
- 以整个数组的中间部分为分界点,分割
- ② 递归排序左边和右边
- ③ 归并(★难点)
- 将两个有序的数组合并成一个有序的序列
2- 归并排序代码实现(双指针)
⭐ 归并排序 ——实现思路
static void merge_sort(int[] q,int l,int r){
if(l>=r) return;
int mid = (l+r)/2; //1. 选择分界点
merge_sort(q,l,mid); // 2. 递归排序左侧和右侧,使左右两边都有序
merge_sort(q,mid+1,r);
int i = l; // i 是左侧数组起点
int j = mid+1; // j是右侧数组起点
int k = 0; // k是代表已经合并的元素个数
int[] tmp = new int[r-l+1]; //辅助数组
while(i <= mid && j <= r){ //3.归并左右两端
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(i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j]; // 取出辅助数组中的元素
}
3- ACM模式实现
public class merge {
public static void mergeSort(int[] nums,int l,int r){
if(l>=r) return;
int mid = (l+r)/2;
mergeSort(nums,l,mid);
mergeSort(nums,mid+1,r);
// 单层逻辑
int i = l;
int j = mid+1;
int k = 0;
int[] tmp = new int[r-l+1];
while(i<=mid && j<=r){
if(nums[i]<=nums[j]){
tmp[k++] = nums[i++];
}else{
tmp[k++] = nums[j++];
}
}
// 两个
while(i<=mid) tmp[k++] = nums[i++];
while(j<=r) tmp[k++] = nums[j++];
// 将 tmp 赋值给 q
for(i = l,j=0; i<=r ;i++,j++){
nums[i] = tmp[j];
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("输入数组长度");
int n = sc.nextInt();
System.out.println("输入数组值");
int[] num = new int[n];
for(int i = 0 ; i < n;i++){
num[i] = sc.nextInt();
}
mergeSort(num,0,num.length-1);
for(int res:num){
System.out.print(res+" ");
}
}
}