手撕归并排序

1.思想1分治策略 合并有序数组。2将数组不断对半分成子数组。3排序后合并有序子数组。2.算法步骤1分解将数组从中间分成两半。2递归对左右两半分别归并排序。3合并将两个有序子数组合并成一个有序数组。3.复杂度与特点1时间复杂度始终为O(nlogn)无论好坏。2空间复杂度O(n)需要额外数组存储排序结果。3归并排序是否稳定稳定合并时会保持相等的元素顺序。4特点数据不敏感可轻松用于链表排序。附代码class MergeSort { // 归并排序主方法 public void mergeSort(int[] nums, int left, int right) { if (left right) { return; } int mid left (right - left) / 2; // 递归排序左半部分 mergeSort(nums, left, mid); // 递归排序右半部分 mergeSort(nums, mid 1, right); // 合并两个有序子数组 merge(nums, left, mid, right); } // 合并方法 private void merge(int[] nums, int left, int mid, int right) { // 创建临时数组 int[] temp new int[right - left 1]; int i left; // 左半部分指针 int j mid 1; // 右半部分指针 int k 0; // 临时数组指针 // 比较两个子数组的元素将较小的放入临时数组 while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { temp[k] nums[j]; } } // 将左半部分剩余元素复制到临时数组 while (i mid) { temp[k] nums[i]; } // 将右半部分剩余元素复制到临时数组 while (j right) { temp[k] nums[j]; } // 将临时数组的元素复制回原数组 for (i 0; i temp.length; i) { nums[left i] temp[i]; } } }ACM模式import java.util.Scanner; class MergeSort { // 归并排序主方法 public void mergeSort(int[] nums, int left, int right) { if (left right) { return; } int mid left (right - left) / 2; // 递归排序左半部分 mergeSort(nums, left, mid); // 递归排序右半部分 mergeSort(nums, mid 1, right); // 合并两个有序子数组 merge(nums, left, mid, right); } // 合并方法 private void merge(int[] nums, int left, int mid, int right) { // 创建临时数组 int[] temp new int[right - left 1]; int i left; // 左半部分指针 int j mid 1; // 右半部分指针 int k 0; // 临时数组指针 // 比较两个子数组的元素将较小的放入临时数组 while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { temp[k] nums[j]; } } // 将左半部分剩余元素复制到临时数组 while (i mid) { temp[k] nums[i]; } // 将右半部分剩余元素复制到临时数组 while (j right) { temp[k] nums[j]; } // 将临时数组的元素复制回原数组 for (i 0; i temp.length; i) { nums[left i] temp[i]; } } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取数组长度 int n scanner.nextInt(); // 读取数组元素 int[] nums new int[n]; for (int i 0; i n; i) { nums[i] scanner.nextInt(); } // 归并排序 MergeSort mergeSort new MergeSort(); mergeSort.mergeSort(nums, 0, n - 1); // 输出排序结果 for(int i 0;i n;i){ System.out.print(nums[i]); if(i n - 1){ System.out.print( ); } } System.out.println(); scanner.close(); } }