归并排序

阅读量: 513 编辑

归并排序 - mergeSort

该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

一、算法步骤

  • 1、将一个数组拆分为两个,从中间点拆开,通过递归操作来实现一层一层拆分。

  • 2、从左右数组中选择小的元素放入到临时空间,并移动下标到下一位置。

  • 3、重复步骤2直到某一下标达到尾部。

  • 4、将另一序列剩下的所有元素依次放入临时空间。

  • 5、将临时空间的数据依次放入原数据数组。

二、Java代码

//归并排序:正序排列
public static int[] temp = null;

public static void mergeSort(int[] array, int left, int right) {
    if (temp == null) {
        temp = new int[array.length];
    }

    //结束递归
    if (left >= right) {
        return;
    }

    //取中值
    int mid = (left + right) / 2;
    
    //递归
    mergeSort(array, left, mid);
    mergeSort(array, mid + 1, right);

    //合并
    int k = 0, i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }

    //多余的已经排序的数写入临时数组
    while (j <= right) {
        temp[k++] = array[j++];
    }

    while (i <= mid) {
        temp[k++] = array[i++];
    }

    //写入原数组
    for (i = left, j = 0; i <= right; i++, j++) {
        array[i] = temp[j];
    }

}

三、代码总结

苏ICP备13052010号-3
©2022 南京匠成信息科技有限公司