归并排序

一、概念

归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。这里我们主要讲的是两路归并。

归并排序的最大特点是稳定 ，平均复杂度为 O(Nlogn)

二、思路

• 将一个长度为n的无序数组看成n个长度为1的数组。
• 进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表。
• 重复第二步直到所有记录归并成一个长度为 n 的有序表为止。

这里推荐一个可视化在线学习网站, visualgo，里面有各种数据结构和算法的可视化过程。

例如: {14,12,15,13,11,16} 这个数组它的排序过程如下图。

归并排序过程.png

三、代码实现

    /**
     * 归并排序
     * @param arr 
     * @param low
     * @param high
     */
    public static void mergeSort(int [] arr, int low, int high) {
        if (low >= high) {
           return;
        }
        
        int mid = (low + high) / 2;
        // 二路归并就是分两部分，多路归并里面写多个sort 就行了
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
    
    /**
     * 归并
     * @param arr
     * @param low
     * @param mid
     * @param high
     */
    public static void merge(int [] arr, int low, int mid, int high) {
        int[] tmp = new int[arr.length];

        int i = mid + 1; // 右边的指针
        int j = low;  // 左边的指针
        int k = low; //合并后的数组指针

        // 依次归并
        while(low <= mid && i <= high) {
            // 将小的依次放入tmp数组
            if (arr[low] <= arr[i]) {
                tmp[j++] = arr[low++];
            } else {
                tmp[j++] = arr[i++];
            }
        }

        //左边归并
        while (low <= mid) {
            tmp[j++] = arr[low++];
        }

        // 右边归并
        while (i <= high) {
            tmp[j++] = arr[i++];
        }

        // 将tmp数组中的数据写入原数组中
        System.out.println("第"+(++number)+"趟排序:\t");
        while (k <= high) {
            arr[k] = tmp[k];
            //输出中间归并排序结果
            System.out.print(arr[k]+"\t");
            k++;
        }
        System.out.println();
    }


    private static void printArray(String pre,int[] a) {
        System.out.print(pre + "\n");
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + "\t");
        System.out.println();
    }

    private static int number = 0;
    @Test
    public void testMergeSort() {
        int[] a = {14,12,15,13,11,16 };
        printArray("排序前：",a);
        mergeSort(a, 0, a.length - 1);
        printArray("排序后：",a);
    }

排序结果.png