星星博客 »  > 

归并排序

public class test {

    public static void mergeSort(int array[], int L, int M, int R) {

        //何为归并 划分为归 合并则为并  合并需要两边的数组都是排好序的,所以用递归将大化小,然后合并成排序好的数组
        //然后直到最后两个大数组,合并起来就是答案了
        int LEFT_SIZE = M - L + 1; //4    左边数组大小
        int RIGHT_SIZE = R - M; //4       右边数组大小
        int[] LEFT_ARRAY = new int[LEFT_SIZE];   // 创建左数组
        int[] RIGHT_ARRAY = new int[RIGHT_SIZE]; // 创建右数组

        int i; //定义三个变量 
        int j;
        int k = L; //其中k很重要

        //用两个for循环将大的数组分成两个数组
        for (i = 0; i < LEFT_SIZE; i++) {
            LEFT_ARRAY[i] = array[k];
            k++;
        }

        for (i = 0; i < LEFT_SIZE; i++) {
            RIGHT_ARRAY[i] = array[k];
            k++;
        }

//        for (i = 0; i < LEFT_SIZE; i++) {
//            System.out.print(LEFT_ARRAY[i] + " ");
//        }
//        System.out.println();
//        for (i = 0; i < RIGHT_SIZE; i++) {
//            System.out.print(RIGHT_ARRAY[i] + " ");
//        }

        // 全部重新初始化
        i = 0;
        j = 0;
        k = L;

        //循环比较亮边数组的头指针指向的数字的大小,然后放到大数组中
        while (i < LEFT_SIZE && j < RIGHT_SIZE) {
            if (LEFT_ARRAY[i] < RIGHT_ARRAY[j]) {
                array[k] = LEFT_ARRAY[i];
                i++;
                k++;
            } else {
                array[k] = RIGHT_ARRAY[j];
                j++;
                k++;
            }
        }
        //如果有哪一边没有放完,就把那一边全部给依次给放进去
        if (i == LEFT_SIZE && j < RIGHT_SIZE) {
            while (j < RIGHT_SIZE) {
                array[k] = RIGHT_ARRAY[j];
                k++;
                j++;
            }
        } else if (j == RIGHT_SIZE && i < LEFT_SIZE) {
            while (i < LEFT_SIZE) {
                array[k] = LEFT_ARRAY[i];
                k++;
                i++;
            }
        }

//        System.out.println();
//        for (i = L; i <= R; i++) {
//            System.out.println(array[i]);
//        }

    }

    public static void mergesSplit(int array[], int L, int R) {
        if (L == R) return;
        int M = (L + R) / 2;
        mergesSplit(array, L, M);
        mergesSplit(array, M + 1, R);
        mergeSort(array, L, M, R);
    }


    public static void main(String[] args) {
//        int[] array = {2, 8, 19, 35, 4, 6, 15, 49};// L=0 R=7 M=3
        int[] array = {6, 2, 35, 15, 21, 12, 26, 48};
        int L = 0;
        int R = array.length - 1;
        int M = (L + R) / 2;
        mergesSplit(array, L, R);

        for (int i = 0; i <= R; i++) {
            System.out.println(array[i]);
        }

    }
}

相关文章