java归并排序

package datastruct;

/**
 * Created by Zephery on 2017/3/3.
 */
public class Solution {
    public static void printArray(int[] arr, int i, int j) {
        System.out.print("[");
        for (int k = i; k < j; k++) {
            System.out.print(arr[k] + ",");
        }
        System.out.print(arr[j] + "]");
    }

    private static void mergesort(int[] arr, int i, int j) {
        int mid = 0;
        if (i < j) {
            mid = (i + j) / 2;
            mergesort(arr, i, mid);
            mergesort(arr, mid + 1, j);
            merge(arr, i, mid, j);
        }
    }

    private static void merge(int[] arr, int i, int mid, int j) {
        System.out.print("Left:");
        printArray(arr, i, mid);
        System.out.println("Right:");
        printArray(arr, mid + 1, j);
        System.out.println();
        int temp[] = new int[arr.length];
        int l = i;
        int r = j;
        int m = mid + 1;
        int k = l;
        while (l <= mid && m <= r) {
            if (arr[l] <= arr[m]) {
                temp[k++] = arr[l++];
            } else {
                temp[k++] = arr[m++];
            }
        }
        while (l <= mid) {
            temp[k++] = arr[l++];
        }
        while (m <= r) {
            temp[k++] = arr[m++];
        }
        for (int i1 = i; i1 <= j; i1++) {
            arr[i1] = temp[i1];
        }
        System.out.print("After Merge:");
        printArray(arr, i, j);
        System.out.println();
    }

    public static void main(String args[]) {
        int[] arr = {9, 4, 8, 3, 1, 2, 5};
        System.out.print("Initial Array:");
        printArray(arr, 0, arr.length - 1);
        System.out.println();
        mergesort(arr, 0, arr.length - 1);
    }
}
Initial Array:[9,4,8,3,1,2,5]
Left:[9]Right:
[4]
After Merge:[4,9]
Left:[8]Right:
[3]
After Merge:[3,8]
Left:[4,9]Right:
[3,8]
After Merge:[3,4,8,9]
Left:[1]Right:
[2]
After Merge:[1,2]
Left:[1,2]Right:
[5]
After Merge:[1,2,5]
Left:[3,4,8,9]Right:
[1,2,5]
After Merge:[1,2,3,4,5,8,9]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区