归并排序

归并排序

public class MergeSort {

    public static void main(String[] args) {
        int[] array = {-1,10,8,100,72,33,46};
        mergeSort(array, 0, array.length - 1, new int[array.length]);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 归并排序：分治思想 先拆分，后合并
     *
     * @param array
     */
    public static void mergeSort(int[] array, int left, int right, int[] copyArray) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid, copyArray);
            mergeSort(array, mid + 1, right, copyArray);
            mergeAsc(array, left, mid, right, copyArray);
            //mergeDesc(array, left, mid, right, copyArray);
        }
    }




    /**
     * 合并的方法   数组左右两边均为有序数列，左右两边元素依次比较 将较小的元素copy至temp中，
     * 依次循环直至一边有剩余数据，将剩余的数据copy至temp中
     * @param array
     * @param startIndex
     * @param mid
     * @param endIndex
     * @param temp
     * 归并排序 合并的方法 升序
     */
    public static void mergeAsc(int[] array,int startIndex,int mid,int endIndex,int[] temp) {
        int left = startIndex;
        int right = mid + 1;
        int t = 0;
        while (left <= mid && right <= endIndex) {
            if (array[left] <= array[right]) {
                temp[t] = array[left];
                t++;
                left++;
            } else {
                temp[t] = array[right];
                t++;
                right++;
            }
        }

        while (left <= mid) {
            //左边数据有剩余
            temp[t] = array[left];
            t++;
            left++;
        }

        while (right <= endIndex) {
            //右边有剩余
            temp[t] = array[right];
            t++;
            right++;
        }

        //将temp中的数据还原至原数组中
        t = 0;
        int tempLeft = startIndex;
        while (tempLeft <= endIndex) {
            array[tempLeft] = temp[t];
            tempLeft++;
            t++;
        }
    }


    public static void mergeDesc(int[] array, int startIndex,int mid,int endIndex,int[] temp){
        int left = startIndex;
        int right = mid + 1;
        int t = 0;
        while (left <= mid && right <= endIndex) {
            if (array[left] > array[right]) {
                temp[t] = array[left];
                left++;
                t++;
            } else {
                temp[t] = array[right];
                right++;
                t++;
            }
        }

        while (left <= mid) {
            temp[t] = array[left];
            left++;
            t++;
        }

        while (right <= endIndex) {
            temp[t] = array[right];
            right++;
            t++;
        }

        t = 0;
        int tempLeft = startIndex;
        while(tempLeft <= endIndex) {
            array[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }


    }
}