一、归并排序

什么是归并排序

归并排序就是将两个有序的子序列合并到一个序列中。是分治算法的一个典型应用，什么是分治算法呢？分治算法就是利用算法将一个原问题分解成一个个子问题（子问题与原问题的性质一样），分别计算出每个子问题的最优解，即可求出原问题的解；最简单的就是问题就是二分法问题，归并排序正是分治算法的二分法问题；

分治算法可以使用递归或者动态规划等思想，将复杂问题简单化。

归并排序的使用场景

当空间内存比较充足，数据量有比较大的时候，为了更好的完成排序效率，推荐使用归并排序，其时间复杂度为O(N*logN)；

归并排序的实现方式

结合递归思想，将一个需要排序的数组，反复的两半切割成子数组，直到得到的子数组只含有一个数据项（基值条件）；

然后将每个切成的子数组使用归并进行合并到一个数组中，反复执行，最后得到一个有序的数组。

public class TestMain {

    public  static int[] a = {1, 4, 5, 11, 2, 7, 6, 9, 8, 12, 66, 33, 55};

    public static void main(String[] args) {

        int[] arraySpace = new int[a.length];

        recMerge(arraySpace,0,a.length-1);

        for (int i = 0; i < arraySpace.length; i++) {

            System.out.println(arraySpace[i]);

        }

    }

 

    private static void recMerge(int[] arraySpace, int lower, int upper) {

        // 基值条件：如果两个下标值相等，说明不能在分割了，直接返回

        if (lower == upper) {

            return;

        }

        // 采用二分法的分治思想，拆分两个子数组，最后采用归并排序

        int mid = (lower + upper) / 2;

        recMerge(arraySpace, lower,mid);

        recMerge(arraySpace,mid+1,upper);

        merge(arraySpace,lower,mid+1,upper);

    }

    private static void merge(int[] arraySpace, int lower, int mid,int upper) {

        int size = upper - lower + 1; //本次归并的个数

        int index = 0;

        int lowerIndex = lower; // 记录一开始的位置

        int midIndex = mid - 1; // 记录中间的位置

        //当两边都有值时，进行比较排序

        while (lower <= midIndex && mid <= upper) {

                if (a[lower] < a[mid]) {

                    arraySpace[index++] = a[lower++];

                }else {

                    arraySpace[index++] = a[mid++];

                }

        }

        // 当右边比较完并完成排序，只剩左边的值，则直接插入

        while (lower <= midIndex) {

            arraySpace[index++] = a[lower++];

        }

        //当左边比较完并完成排序，只剩右边的值，则直接插入

        while (mid <= upper) {

            arraySpace[index++] = a[mid++];

        }

        // 最后将归并排序完的数组，复制到原数组中，等待下一次归并排序，直到最后完整排序完

        for (int i = 0; i < size; i++) {

            a[lowerIndex++] = arraySpace[i];

        }

    }

}

归并排序的优缺点

归并排序的优点很明显：时间复杂度比较快：O(N*logN)。

归并排序缺点也很明显，就是浪费空间。第一是需要单独一块空间存放归并数据，第二就是每次归并完都需要将其复制到原数组中，特别浪费空间，如果空间内存不足的，请慎重使用。事实上，所说的缺点大多是由于归并排序使用的递归算法，也就是分治思想，带来的问题，虽然利用分治思想可以很好的解决我们的实际问题，但是实际中它的效率并不高；因此呢，如果我们想要追求高效率，那么我们可以考虑一下怎么消除递归等方法，常用的方法一般是利用循环或者栈来代替

注意一下：

大多数递归算法都可以用栈结构来代替，例如我们的编译器在处理方法函数的调用的时候，我们会遇到方法函数内还有存在一层层的其他方法函数的调用，就跟递归的原理一样，一层层的调用，直到最后一层，然后再一层层的返回；编译器利用了栈来实现这种思想，将方法名、参数和返回值地址一层层的压入栈中，利用先进后出的特性，最后返回到最开始调用的那个方法函数里，用栈消除递归，效率更高更可靠。

二、希尔排序

public class TestMain {
    public  static int[] a = {1, 4, 5, 11, 2, 7, 6, 9, 8, 12, 66, 33, 55};
    public static void main(String[] args) {
        shellSort(a,a.length);
        for (int i = 0; i < a.length; i++) {
            System.out.print(" "+a[i]);
        }
    }
    private static void shellSort(int[] arraySort,int size) {
        int h = 1; // 计算出间隔序列大小值
        while (h <= size/3) { // 范围公式可以自己定义一个合适的范围
            h = h*3 +1;
        }
        int inner,outer;
        int temp;// 开辟一个临时变量空间保存插入排序的腾出空位置的元素
        while (h > 0) {
            for (outer = h; outer < size ; outer++) {
                temp = arraySort[outer];
                inner = outer;
                while (inner > h-1 && arraySort[inner - h] >= temp) {
                    arraySort[inner] = arraySort[inner - h];
                    inner -= h;
                arraySort[inner] = temp;
            }
            h = (h -1) / 3; // 逆置间隔序列
        }
    }
}

If(h < 5) {
     h = 1;
} else {
     h = (5*h - 1) / 11;
}

public class TestMain {

    public  static int[] a = {1, 4, 5, 11, 2, 7, 6, 9, 8, 12, 66, 33, 55};

    public static void main(String[] args) {

        quickSort(0,a.length-1,a);

        for (int i = 0; i < a.length; i++) {

            System.out.print(" "+a[i]);

        }

    }

    private static void quickSort (int left,int right, int[] array) {

        // 由于使用递归思想，此处为递归的基值条件
        if (left >= right) {
            return;
        }

        // 选择数组中的一个数据项作为枢纽，本次选择最右端的数据项作为枢纽
        int pivot = array[right];

        // 对数组进行左右子数组进行划分，将枢纽位置与右子数组的第一位置交换，最后返回枢纽位置
        int part = partition(left,right,pivot,array);

        // 对划分好的左子数组进行递归快速排序
        quickSort(left,part -1, array);

        // 对划分好的右子数组进行递归快速排序
        quickSort(part + 1,right,array);

    }

 

    private static int partition(int left, int right, int pivot,int[] array) {

        int leftPtr = left;

        int rightPtr = right;

        while (true) {

            while (array[leftPtr] < pivot) {
                ++leftPtr;
            }

            while (rightPtr > 0 && array[--rightPtr] > pivot){
            }

            if (leftPtr >= rightPtr) {
                break;
            }

            // 交换位置，移到枢纽的正确两边
            swap(leftPtr,rightPtr,array);
        }

        // 最后将枢纽的位置与右边子数组的第一个位置进行值交换
        swap(leftPtr,right,array);

        // 返回枢纽位置
        return leftPtr;
    }

    private static void swap(int index1,int index2,int[] array) {

        int temp = array[index1];

        array[index1] = array[index2];

        array[index2] = temp;

    }

}