排序-归并

今天记录下关于：归并排序一些理解和心得。
主要分为以下几个方面分享

• 归并排序的思想
• 实现方式
• 时间复杂度
• 应用

归并排序的思想

实现方式

    public static void main(String[] args){
        Integer[] array = Util.createRandomArray(1000, 30);
        Integer[] array2 = Arrays.copyOf(array, array.length);
        Integer[] array3 = Arrays.copyOf(array, array.length);

        //调用Arrays.sort()
        Util.sysSort(array2);
        Util.print(array2, "Arrays.sort--");

        System.out.println("--------------------------------------------------------------------");

        //归并排序
        Integer[] result = mergeSort(array3);
        Util.print(result, " Merge Sort--");
    }

    public static Integer[] mergeSort(Integer[] array){
        //FIXME 要点
        //先排序
        //再合并

        if(array == null || array.length == 1){
            return array;
        }

        Integer[] result;

        //退出条件
        int length = array.length;
        if(length == 1){
            result = array;

        } else if(length == 2){
            swap(0, 1, array);
            result = array;

        } else {
            Integer[] left = new Integer[array.length >> 1];
            Integer[] right = new Integer[array.length - left.length];
            System.arraycopy(array, 0, left, 0, left.length);
            System.arraycopy(array, left.length, right, 0, right.length);

            left = mergeSort(left);
            right = mergeSort(right);

            result = merge(left, right);
        }

        return result;
    }

    private static Integer[] merge(Integer[] left, Integer[] right){
        Integer[] result = new Integer[left.length + right.length];

        int leftIndex = 0;
        int rightIndex = 0;
        int resultIndex = 0;
        while(leftIndex < left.length && rightIndex < right.length){
            Integer temp;

            if(left[leftIndex] < right[rightIndex]){
                temp = left[leftIndex++];
            } else {
                temp = right[rightIndex++];
            }

            result[resultIndex++] = temp;
        }

        while(leftIndex < left.length){
            result[resultIndex++] = left[leftIndex++];
        }

        while(rightIndex < right.length){
            result[resultIndex++] = right[rightIndex++];
        }

        return result;
    }

    private static void swap(int left, int right, Integer[] array){
        if(array[left] <= array[right]){
            return;
        }

        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

log

Arrays.sort--:53---63---119---127---133---192---222---242---328---328---428---511---598---607---618---640---656---667---675---695---700---701---730---794---812---825---842---872---896---921
--------------------------------------------------------------------
 Merge Sort--:53---63---119---127---133---192---222---242---328---328---428---511---598---607---618---640---656---667---675---695---700---701---730---794---812---825---842---872---896---921

时间复杂度

应用