关于数据结构:归并排序

什么是归并排序？？

归并排序是基于归并的排序。归并，是将两个或两个以上的有序表合成一个有序表。

假如待排序的数组有 n 个元素，将数组看成是 n 个有序的子数组，每个子数组只有一个元素。而后两两合并，失去每个子数组长度为 2。而后持续两两合并，直到合并为长度为 n 的数组。

工夫复杂度

均匀复杂度是 O(nlogn)，最好复杂度是 O(nlogn)，最坏复杂度是 O(nlogn)。

（图片来源于网络）

将原数组划分子数组的过程看成是一棵二叉树，那么数组划分到每个子数组中只有一个元素时的二叉树高度（递归深度）。最初一层是叶子节点，每个叶子节点是一个元素。那么，最初一层的节点个数是 n（数组长度）。假如二叉树深度是 k，那么，从 2^(k-1) = n 失去，k 是 logn。合并的过程是从子数组（其中只有一个元素）开始向上合并

每次排序须要遍历一次数组，工夫是 O(n)。一共须要 logn 趟排序（二叉树的深度，递归深度）。所以工夫复杂度是 O(nlogn)。

空间复杂度

空间复杂度是 O(n) 。

每次排序中都须要一个数组临时保留排序前的数组或者是排序后的后果数组，数组占用的空间是 n（数组的长度）。

应用场景

归并排序是稳固的排序。也就是，相等的元素的程序不会扭转。归并排序的速度仅次于疾速排序。个别用于总体是无序的，然而子序列是绝对有序的。

public void sort(int[] array)  {mergeSort(array, 0, array.length);
}

public void mergeSort(int[] array, int low, int high) {if (low >= high) return;
    int mid = (low + high) / 2;  // 将数组一分为二
    mergeSort(array, 0, mid);  // 对右边一半进行排序
    mergeSort(array, mid, high);  // 对左边一半进行排序
    merge(array, low, mid, high);  // 将两个有序子数组合并为一个有序数组
}

// 将数组左右两半合并为一个排好序的数组。左右两个子数组曾经是排好序的数组
public void merge(int[] array, int low, int mid, int high) {
    // 将数组 array 复制到一个新数组 copy 中，将排序实现后的值写入原数组 array
    int[] copy = Arrays.copyOf(array, array.length);  // 复制
    int i = low, j = mid, k = low;
    // 逐个比拟两个子数组，小者排在后面。直至其中一个数组全副写入后果数组中
    while (i < mid && j < high) {if (copy[i] <= copy[j]) array[k++] = copy[i++];  // 相等的元素，绝对地位不扭转
        else array[k++] = copy[j++];
    }
    // 如果右边的子数组中残余的数据写入数组中
    while (i < low) array[k++] = copy[i++];
    // 如果左边的子数组中残余的数据写入数组中
    while (j < high) array[k++] = copy[j++];
}

/**********************************************************************/
// 将两个有序子数组合并为一个有序数组。第一个有序子数组是[low,mid)，第二个有序子数组是[mid,high)
public void merge(int[] array, int low, int mid, int high) {
    // 将数组 array 复制到一个新数组 copy 中，将排序实现后的值写入原数组 array
    int[] res = new int[array.length];  // 复制
    int i = low, j = mid, k = low;
    // 逐个比拟两个子数组，小者排在后面。直至其中一个数组全副写入后果数组中
    while (i < mid && j < high) {if (array[i] <= array[j]) res[k++] = array[i++];
        else res[k++] = array[j++];
    }
    // 如果右边的子数组中残余的数据写入数组中
    while (i < low) res[k++] = array[i++];
    // 如果左边的子数组中残余的数据写入数组中
    while (j < high) res[k++] = array[j++];

    // 把后果数组 res 中 [low,high) 中的局部复制到原数组中，从而扭转原数组
    for (i = low, k = low; i < high; i++, k++) {array[k] = res[i];
    }
}

public void mergeSort(int[] array, int low, int high) {if (low >= high) return;
    int mid = (low + high) / 2;  // 将数组一分为二
    mergeSort(array, 0, mid);  // 对右边一半进行排序
    mergeSort(array, mid, high);  // 对左边一半进行排序
    merge(array, low, mid, high);  // 将排好序的两局部合并为一个排好序的数组
}

mergeSort() 是一个递归函数。递归的过程就像是一个下楼梯的过程。在递归时，调用一次本人，就下一个台阶（调用），直到下到最初一个（终止条件），而后想上返回到第一个台阶（回溯）。

归并排序，向下划分，向上合并 的过程。在向下调用本身的过程，把数组一分为二，一次次的划分，直到数组中的一个元素独自成为一个子数组。mergeSort(array, low, mid) 和mergeSort(array, mid, high) 是调用本身划分的过程。合并是产生在划分之后，merge(array, low, mid, high) 是把两个升序的子数组合并为一个升序的数组，也是递归中回溯做的事件。

关于数据结构:归并排序

1. 根本思维

2. 代码实现（java）

3. 代码阐明