算法学习记录2 归并排序

自己的理解

归并排序感觉比快速排序简单一点...反正我觉得好理解一点..

1.把1个要排序的数组拆分成2个要排序的小数组(可以直接取中间元素,分成2个一样长度的小数组).

2.对每个小数组继续拆分,拆分到只有一个元素.

3.把2个小数组重合归并成一个排好序的大数组,然后这个大数组再和其他大数组归并成一个更大的数组....循环下去最后归并成一开始完整的数组.

 

实现

package algorithm;

import java.util.Arrays;

/**
 * 合并排序
 * 
 * @author [e-mail]
 * @since 2017年2月27日 上午10:25:48
 */
public class MergeSortTest1 {
    public static void main(String[] args) {
        int[] arr1 = { 4, 7, 5, 6, 1, 3, 8 };
        int[] arr2 = { 7, 6, 5, 4, 3, 2, 1 };
        int[] arr3 = { 5, 9, 3, 7, 8, 6, 1, 2, 4 };
        int[] arr4 = { 13, 2, 5, 4, 88, 76, 68, 87, 55, 88, 88, 77, 67, 99, 100, 5, 53, 52, 51, 66 };
        sort(arr1);
        sort(arr2);
        sort(arr3);
        sort(arr4);
        System.out.println(Arrays.toString(arr1));
        System.out.println(Arrays.toString(arr2));
        System.out.println(Arrays.toString(arr3));
        System.out.println(Arrays.toString(arr4));
    }

    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 排序,可以只排序low到high的位置的数字
     * 
     * @param arr
     *            待排序数组
     * @param low
     *            要排序数组的开始下标位置
     * @param high
     *            要排序数组的终止下标位置
     */
    private static void sort(int[] arr, int low, int high) {
        // 先把数组拆分再合并
        if (low == high) { // 当数组只有1个元素的时候不需要再拆分
            return;
        }
        int mid = (low + high) / 2;// 准备把数组拆分成2个小部分
        sort(arr, low, mid);// 再把前半部分再拆分成1半和1半
        sort(arr, mid + 1, high);// 再把后半部分再拆分成1半和1半
        merge(arr, low, high, mid);// 把各自排好序的两部分合并起来.合并时候也需要重新排下序,因为虽然2个小部分是排好序的,但是不能保证一个小部分的每个元素都比另外一部分大或者小,可能也有交叉.
    }

    /**
     * 把各自排好序的2部分合并起来(需要重新排下序)
     * 
     * @param arr
     *            带排序数组
     * @param low
     *            两部分最小的下标
     * @param high
     *            两部分最大的下标
     * @param mid
     *            左半部分最后一个数字的下标
     */
    private static void merge(int[] arr, int low, int high, int mid) {
        int[] temp = new int[high - low + 1]; // 2部分总共有多少个数字,排好序存放在这个数组里
        int leftPointer = low;// 左半部分最小的下标
        int rightPointer = mid + 1;// 右半部分最小的下标
        int currPointer = 0;// 遍历temp用
        while (leftPointer <= mid && rightPointer <= high) { // 左半部分循环结束或者右半部分循环结束
            if (arr[leftPointer] <= arr[rightPointer]) { // 左边数组的数字<=右边数组的数字
                temp[currPointer++] = arr[leftPointer++];// 把左边的数字放到temp中,然后currPointer指向temp中下一个空着的位置,左边数字的指针向后移动
            } else {// 左边数组的数字>右边数组的数字
                temp[currPointer++] = arr[rightPointer++];// 把右边的数字放到temp中,然后currPointer指向temp中下一个空着的位置,右边数字的指针向后移动
            }
        }
        // while结束的时候肯定至少有一个数组所有元素已经全部放到temp里了
        if (leftPointer > mid) { // 如果左边的数组已经全部拷贝到temp里了
            for (int i = rightPointer; i <= high;) {
                temp[currPointer++] = arr[i++];// 把右边剩下的元素拷贝到temp里
            }
        }

        if (rightPointer > high) { // 如果右边的数组已经全部拷贝到temp里了
            for (int i = leftPointer; i <= mid;) {
                temp[currPointer++] = arr[i++];// 把左边剩下的元素拷贝到temp里
            }
        }

        // 把temp覆盖回arr的low-high的位置
        int tempPointer = low;
        for (int i = 0; i < temp.length; i++) {
            arr[tempPointer++] = temp[i];
        }
    }
}