算法(四)归并排序

归并排序是一个效率相对较高的排序算法，它采用的是分治的思想，将待排序的序列分成若干组，保证每组都有序，然后再进行合并排序，最终使整个序列有序。

基本步骤

1. 将待排序的序列采用分治思想将其划分成若干组，使其有序，其中可采用递归进行划分。
2. 将有序的组分别进行归并操作，其中借助一个辅助数组，将左右划分的有序组从头开始进行比较，将较小的数加入到辅助数组中，且较小的所在有序数组向后自增，再与原来比较的数进行比较。
3. 重复上面2的步骤，直到所有数据比较完毕，或者将还有剩余数未比较的有序数据直接按原有的顺序加入到辅助数组中,最后将已经排好序的辅助数组加入到原有数组的相应位置。
4. 重复上面的2、3步骤，直到所有的左右划分归并完毕。

根据步骤我们可以先对两个有序序列归并的操作进行实现

实现

合并

按照上面的2、3步骤，实现合并操作

public static void merge(int[] arr, int low, int mid, int height) {
        int i = low;
        int j = mid + 1;
        int k = 0;
        int[] temp = new int[height - low + 1];
        while (i <= mid && j <= height) {
            if (arr[i] <= arr[j]) {//左边加入
                temp[k++] = arr[i++];
            } else {//右边加入
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {//左边剩余全部加入
            temp[k++] = arr[i++];
        }

        while (j <= height) {//右边剩余全部加入
            temp[k++] = arr[j++];
        }

        for (int m = 0; m < temp.length; m++) {//辅助数组还原到原数组
            arr[low + m] = temp[m];
        }
    }

下面就是采用分治进行划分

分治

这里可能会有疑问，如何将划分的序列生成有序序列，因为我们采用的是分治的思想与递归思想，只要序列能进行划分，我们就一直划分下去，直到划分的序列只有一个数据时，该划分的序列自然就有序了，同时再进行合并，自然合并的序列也就一直有序了。

public static void mergeSort(int[] arr, int low, int height) {
        if (low < height) {
            int mid = (low + height) / 2;
            mergeSort(arr, low, mid);//左划分
            mergeSort(arr, mid + 1, height);//右划分
            merge(arr, low, mid, height);//左右归并
        }
    }

总结

归并排序为稳定排序，排序后相同数的相对位置不会发生改变。由上面的思想可知，将序列划分成组需要logn次，将划分的组合并的时间复杂度为O(n)，所以最终的时间复杂度为O(nlogn)。所以通过时间复杂度，我们可以发现归并排序的效率要比其他的冒泡排序、直接插入排序、直接选择排序等要高。

转载请指明出处 idisfkj博客：https://idisfkj.github.io