排序算法之归并排序

归并排序是分治策略的应用之一，分而治之。
时间复杂度为 O(n log n)
归并排序的思想是:将队列拆分为子队列直到不可分,再将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

核心

归并排序的核心是分治思想和递归实现

• 分治策略：将原问题分解为几个规模较小但类似于原问题的子问题，递归求解这些子问题，然后合并子问题的解来建立原问题的解。

无图无真相，归并排序流程图（盗用百度百科?）

算法分析

• 先将队列递归分解（采用中点分解），直到队列中的元素个数为1
• 分解队列通过计算队列中点，分为左队列（low,mid）和右队列(mid+1,high)
• 当将原队列拆分为最小队列后（队列中只有一个元素），子队列有序
• 将两个有序队列合并为一个有序队列，代码中的mergeArray方法

代码实现

注释比较详细，不做赘述

    /**
     * 
     * @param array 排序数组
     * @param start 开始位置
     * @param end 结束位置
     */
    private void mergeSort(int[] array, int start, int end) {
        if (start < end) {//当数组中的元素不可分时，停止分解
            int mid = (start + end) / 2;//计算中间坐标
            mergeSort(array, start, mid);//递归分解数组
            mergeSort(array, mid + 1, end);//递归分解数组
            //合并数组，合并后为有序数组
            //因为前面为递归调用，所以可以保证第一次调用此方法时，子数组长度为1
            mergeArray(array, start, mid, end);
        }
    }
    
    private void mergeArray(int[] array, int start, int mid, int end) {
        int[] left = new int[mid - start + 1 //存放数据长度
                + 1];//预留安全守卫
        int[] right = new int[end - mid//存放数据长度
                + 1];//预留安全守卫
        System.arraycopy(array, start, left, 0, left.length - 1);
        System.arraycopy(array, mid + 1, right, 0, right.length - 1);

        left[left.length - 1] = SAFE_GUARD;
        right[right.length - 1] = SAFE_GUARD;
        
        int l = 0, r = 0;

        for (int i = start; i <= end; i++) {
            if (right[r] == SAFE_GUARD) {
                array[i] = left[l];
            }
            if (left[l] == SAFE_GUARD) {
                array[i] = right[r];
            }
            if (left[l] <= right[r]) {
                array[i] = left[l];
                l++;
            } else {
                array[i] = right[r];
                r++;
            }
        }
    }

结语

个人认为归并排序重要的是分治思想。JDK7引入了ForkJoinPool也是分治策略的应用。既然如此，需要好好了解下分治策略啦！
《算法导论》第二天，加油！下一篇分治策略