归并排序

归并排序算法思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

分而治之

合并相邻有序子序列

代码实现

import java.util.Arrays;

public class ArrayDemo {
    public static void main(String[] args) {
        //归并排序：

        //治理：将两个有序子序列，合并成一个有序序列
       // int[] arr={1,3,5,7,9,2,4,6,8,10};
        //
        //mergeSort(arr,0,4,arr.length-1);


        int[] arr = {1, 4,6,0,-1,4,9,20,35,98, 9, 2, 4, 6, 8, 10,-4,1000,800};

        chaiFen(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void chaiFen(int[] arr, int startIndext, int endIndex) {
        //计算中间索引
        int centerIndex=(startIndext+endIndex)/2;
        if(startIndext<endIndex){
            //递归拆左边
            chaiFen(arr, startIndext, centerIndex);

            //递归拆右边
            chaiFen(arr, centerIndex + 1, endIndex);

            mergeSort(arr, startIndext, centerIndex, endIndex);

        }


    }

    /**
     *
     * @param arr 要归并排序的数组
     * @param startIndtx 起始索引
     * @param centerIndex 中间索引
     * @param endIndex 结束索引
     */
    private static void mergeSort(int[] arr, int startIndtx, int centerIndex, int endIndex) {
        //定义一个临时数组
        int[] tempArray=new int[endIndex-startIndtx+1];
        //定义第一数组的起始索引
        int i=startIndtx;
        //定义第二个数组的起始索引
        int j=centerIndex+1;
        //定义临时数组的索引
        int index=0;
        //两个数组元素，进行对比归并
        while (i<=centerIndex&&j<=endIndex){
            if(arr[i]<=arr[j]){
                //把小的数放到临时数组中
                tempArray[index]=arr[i];
                i++; //递增一下索引
            }else{
                tempArray[index] = arr[j];
                j++; //递增一下索引
            }
            index++; //临时数组的索引也要递增
        }

        //处理剩余元素
        while (i<=centerIndex){
            tempArray[index]=arr[i];
            i++;
            index++;

        }

        while (j<=endIndex){
            tempArray[index] = arr[j];
            j++;
            index++;

        }

        //经过上面的操作后，临时数组中的元素就排序好了
       // System.out.println(Arrays.toString(tempArray));
        //把临时数组中的元素放到原数组中
        for (int k = 0; k < tempArray.length; k++) {
            arr[startIndtx+k]=tempArray[k];
        }



    }
}