归并排序java示例

归并排序是建立在归并操作上的一种有效的排序算法，该算法采用分治法的思想。分：将待排序序列拆分成一个个子序列。治：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

可以采用递归的方式将待排序序列拆分，然后进行归并操作。

归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置。
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
重复步骤三，直到某一指针超出序列尾。
将另一序列剩下的所有元素直接复制到合并序列尾。

java示例：

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {1,3,2,6,4,66,32,65,34,67,45,67,78,34,56};
        System.out.println("排序前:");
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后:");
        System.out.println(Arrays.toString(arr));
    }

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

    public static void sort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right)/2;
            sort(arr, left, mid);//左边归并排序
            sort(arr, mid + 1, right);//右边归并排序
            merge(arr, left, mid, right);//将两个有序子数组合并处理
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        int[] temp = new int[right - left + 1];//定义临时数据，长度为两个子数组之和
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) {//左边剩余元素放到临时数组里
            temp[t++] = arr[i++];
        }
        while (j <= right) {//右边剩余元素放到临时数组里
            temp[t++] = arr[j++];
        }
        t = 0;
        while (left <= right) {//将临时数组中的元素全部拷贝到原数组中
            arr[left++] = temp[t++];
        }
    }
}

运行结果：

排序前:
[1, 3, 2, 6, 4, 66, 32, 65, 34, 67, 45, 67, 78, 34, 56]
排序后:
[1, 2, 3, 4, 6, 32, 34, 34, 45, 56, 65, 66, 67, 67, 78]

Process finished with exit code 0