希尔排序，归并排序，快速排序（Java实现）

/**
* 希尔排序
* @param arr
* @param gap  增量
*/
private static <T extends Comparable<T>>void shell(T[] arr, int gap) {
        int i = 0, j = 0;
        for (i = gap; i < arr.length; i++) {
            T temp = arr[i];
            for (j = i - gap; j >= 0; j -= gap) {
                if (temp.compareTo(arr[j]) < 0) {
                    arr[j + gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + gap] = temp;
        }
    }

    public static <T extends Comparable<T>>void shellSort(T[] arr) {
        int[] part = {5, 3, 1};
        for (int i = 0; i < part.length; i++) {
            shell(arr, part[i]);
        }
    }

/**
* 归并排序
* @param arr
* @param len
* @param gap
*/
    private static void Merge(int[] arr, int len, int gap) {
        int low1 = 0;//第一个归并段的起始下标
        int high1 = low1 + gap - 1;//第一个归并段的结束下标
        int low2 = high1 + 1;//第二个归并段起始下标
        int high2 = low2 + gap - 1 > len - 1 ? len - 1 : low2 + gap - 1;
        int[] brr = new int[arr.length];
        int i = 0;

        while (low2 < len) {//保证有两个归并段
            while (low1 <= high1 && low2 <= high2) {//两个归并段都有数据时继续判断
                if (arr[low1] <= arr[low2]) {
                    brr[i++] = arr[low1++];
                } else {
                    brr[i++] = arr[low2++];
                }
            }
            while (low1 <= high1) {//第一个归并段还有数据
                brr[i++] = arr[low1++];
            }
            while (low2 <= high2) {
                brr[i++] = arr[low2++];
            }
            low1 = high2 + 1;
            high1 = low1 + gap - 1;
            low2 = high1 + 1;
            high2 = low2 + gap - 1 > len - 1 ? len - 1 : low2 + gap - 1;
        }
        while (low1 <= len - 1) {//没有两个归并段：单的直接拷贝下来
            brr[i++] = arr[low1++];
        }
        for (i = 0; i < arr.length; i++) {
            arr[i] = brr[i];
        }
        brr = null;
    }

    public static void MergeSort(int[] arr) {
        for (int i = 1; i < arr.length; i *= 2) {//2 个 2 个有序，4 个 4 个有序...
            Merge(arr, arr.length, i);
        }
    }

/**
* 快速排序
* @param arr
* @param left
* @param right
*/
    private static <T extends Comparable<T>> int partition(T[] arr, int left, int right) {//快速排序的一趟过程
        T temp = arr[left];
        while (left < right) {
            while (arr[right].compareTo(temp) >= 0 && left < right) {
                right--;
            }
            arr[left] = arr[right];
            while (arr[left].compareTo(temp) <= 0 && left < right) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;
        return left;
    }

    private static <T extends Comparable<T>> void quick(T[] arr, int left, int right) {
        int index = partition(arr, left, right);
        if ((index - left) > 1) {
            partition(arr, left, index - 1);
        }
        if ((right - index) > 1) {
            partition(arr, index + 1, right);
        }
    }

    public static <T extends Comparable<T>> void quickSort(T[] arr, int left, int right) {
        quick(arr, left, right);
    }

public static void main(String[] args) {
        Integer[] arr = {5, 4, 1, 8, 6, 3, 1, 10, 15};
        int[] brr = {5, 4, 1, 8, 6, 3, 1, 10, 15};
//        quickSort(arr,0,arr.length-1);
//        shellSort(arr);
        MergeSort(brr);
//        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(brr));
    }
}