八大排序——归井

 归井

   1.将一个数组拆分成两份（从中间拆开）。

   定义最左侧指针为low，右侧为high，中间指针mid=（low+high）/2

   2.然后通过递归的方法继续拆分

   3.将数组分成一个个的数，然后按顺序合并

   （以一半为例分）

package com.qcby;import java.util.Arrays;public class ShellSort {// 归并排序public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = { 5, 2, 8, 3, 9, 1, 0, 23 };mergeSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}public static void mergeSort(int[] arr, int low, int heigh) {if (low == heigh) {return;}int mid = (low + heigh) / 2;// 拆分mergeSort(arr, low, mid);mergeSort(arr, mid + 1, heigh);// 合并merge(arr, low, mid, heigh);System.out.println(Arrays.toString(arr));}public static void merge(int[] arr, int low, int mid, int heigh) {int s1 = low;int s2 = mid + 1;int[] temp = new int[heigh - low + 1];int i = 0;while (s1 <= mid && s2 <= heigh) {if (arr[s1] <= arr[s2]) {temp[i] = arr[s1];i++;s1++;} else {temp[i] = arr[s2];i++;s2++;}}while (s1 <= mid) {temp[i] = arr[s1];i++;s1++;}while (s2 <= heigh) {temp[i] = arr[s2];i++;s2++;}for (int j = 0; j }