← 返回学习路线

SYSTEM

归并排序

Java基础归并排序system
src/content/notes/system/归并排序.md

归并排序

实现方式

归并排序(Merge Sort):建立在归并操作上的一种有效的排序算法,该算法是采用分治法的典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

实现思路:

  1. 一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止
  2. 将相邻的两个子组进行合并成一个有序的大组
  3. 不断的重复步骤2,直到最终只有一个组为止

归并步骤:每次比较两端最小的值,把最小的值放在辅助数组的左边


实现代码

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
	// low为arr最小索引,high为最大索引
    public static void mergeSort(int[] arr, int low, int high) {
        // low == high 时说明只有一个元素了,直接返回
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(arr, low, mid);		// 归并排序前半段
            mergeSort(arr, mid + 1, high);	// 归并排序后半段
            merge(arr, low, mid, high);		// 将两段有序段合成一段有序段
        }
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        int index = 0;
        // 定义左右指针
        int left = low, right = mid + 1;
        int[] assist = new int[high - low + 1];
        
        while (left <= mid && right <= high) {
            assist[index++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
        }
        while (left <= mid) {
            assist[index++] = arr[left++];
        }
        while (right <= high) {
            assist[index++] = arr[right++];
        }

        for (int k = 0; k < assist.length; k++) {
            arr[low++] = assist[k];
        }
    }
}

用树状图来描述归并,假设元素的个数为 n,那么使用归并排序拆分的次数为 log2(n),即层数,每次归并需要做 n 次对比,最终得出的归并排序的时间复杂度为 log2(n)*n,根据大O推导法则,忽略底数,最终归并排序的时间复杂度为 O(nlogn)

归并排序的缺点:需要申请额外的数组空间,导致空间复杂度提升,是典型的以空间换时间的操作