数据结构与算法（六）排序 插入&希尔&归并

public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {//默认首位已排好序
            int data = arr[i];
            int j = i;
            while (j > 0) {
                if (data > arr[j - 1]) //要排序的元素与前一位比较
                    break;//大则退出
                arr[j] = arr[j - 1];//小则将前一位元素向后移动 留下一个空位
                j--;
            }
            arr[j] = data;//将排序元素赋值给空位
        }
    }

public static void sort(int[] arr) {
        //将元素分组再进行插入排序
        //4, 8, 3, 6, 2, 9 , 5 , 11 , 1
        //n/2=4 步长为4 分为4 2 1| 8 9 | 3 5 | 6 11
        //排序后 1 2 4 | 8 9 | 3 5 | 6 11
        //n/2/2=2 步长为2  1 4 9 5 11|2 8 3 6
        //排序 1 4 5 9 11|2 3 6 8
        //n/2/2/2=1 步长为1 排序后-> 1 2 3 4 5 6 8 9 11
        //最外层为步长循环
        int n = arr.length;
        for (int i = n / 2; i > 0; i = i / 2) { //每次循环步长缩小一半
            for (int j = i; j < n; j++) { //从n/2开始，默认前部分（每个分组的首位）已排好序
                int k = j;
                int data = arr[j];
                while (k >= i) {
                    if (data > arr[k - i])
                        break;
                    arr[k] = arr[k - i];
                    k = k - i;
                }
                arr[k] = data;
            }
        }
    }

public static void sort(int[] arr) {
        //先进行拆分，再进行合并
        split(0, arr.length - 1, arr);
    }
    public static void split(int left, int right, int[] arr) {
        if (left == right) return;
        int mid = (left + right) / 2;//拆分的中间值
        split(left, mid, arr);
        split(mid + 1, right, arr);
        //合
        merge(left, mid, right, arr);
    }
    public static void merge(int left, int mid, int right, int[] arr) {
        int[] temp = new int[right + 1 - left];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j])
                temp[k++] = arr[i++];
            else
                temp[k++] = arr[j++];
        }
        while (i <= mid)
            temp[k++] = arr[i++];
        while (j <= right)
            temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, left, temp.length);
    }