背景

我们上一节复习了三个初级的排序算法（选择，插入，冒泡），这一节我们继续学习时间复杂度优于初级算法的三个算法（希尔，归并，快速），工具类复用上一节的代码。

具体算法

• 希尔算法

/**
 * 希尔排序是根据gap去交换符合gap的相差gap的所有数据提前进行排序
 * 譬如8个数的数组，第一轮gap=4,先判断[0,4],[1,5],[2,6],[3,7]的大小
 * 第二轮gap=2，判断[0,2],[1,3],[2,4],[0-2],[3,5],[1-3]...的大小
 * 第三轮gap=1,再次回归到插入算法，时间复杂度为啥优于插入排序可以参考https://www.zhihu.com/question/24637339
 */
public class ShellSort {

    public static int[] sort(int[] array) {
        if (!SortUtil.safeCheck(array)) {
            return array;
        }
        int length = array.length;

        for (int gap = length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < length; i++) {
                for (int j = i - gap; j >= 0;j -= gap) {
                    if (array[j+gap] < array[j]) {
                        SortUtil.exchange(array, j+gap, j);
                    }
                }
            }
        }
        return array;
    }
}

• 归并排序

/**
 * 首先实现两个数组merge成一个有序数组
 * 利用递归将数组不断分拆成两个数组合并排序即可
 */
public class MergeSort {
    public static int[] sort(int[] array) {
        if (!SortUtil.safeCheck(array)) {
            return array;
        }

        divideAndMerge(array, 0, array.length-1);
        return array;
    }

    /**
     * 合并两个数组成一个有序数组
     */
    private static void merge(int array[], int left, int middle, int right) {
        int leftSize = middle - left;
        int rightSize = right - middle + 1;
        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];

        for (int i = left; i < middle; i++) {
            leftArray[i - left] = array[i];
        }
        for(int i = middle; i <= right; i++) {
            rightArray[i-middle] = array[i];
        }

        int i = 0, j = 0, k = left;
        while (i < leftSize && j < rightSize) {
            if (leftArray[i] < rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }
        while (i < leftSize) {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        while(j < rightSize) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    private static void divideAndMerge(int array[], int left, int right) {
        if (left == right) {
            return;
        }
        int middle = (left + right) / 2;
        divideAndMerge(array, left, middle);
        divideAndMerge(array, middle+1, right);
        merge(array, left, middle+1, right);
    }
}

• 快速排序

/**
 * 首先选择一个基点，然后将小于基点的数放在基点左边，大于基点的数放在基点右边
 * 递归基点左边和右边的数组，但是要特别注意快速不是稳定的算法，因为它是左右两边
 * 顺序是相反的譬如基点66，两个55的数可能后面一个55先判断小于66而提到了前一个55的前面
 */
public class QuickSort {
    public static int[] sort(int[] array) {
        if (!SortUtil.safeCheck(array)) {
            return array;
        }
        divideAndSort(array, 0, array.length -1);
        return array;
    }

    public static int pivotSort(int[] array, int left, int right) {
        int pivot = array[left];
        int k = 0;
        while (left != right) {
            if (k ==0) {
               if (array[right] >= pivot) {
                   right--;
               } else {
                   array[left] = array[right];
                   k++;
               }
            } else if (k == 1) {
                if (array[left] <= pivot) {
                    left++;
                } else {
                    array[right] = array[left];
                    k--;
                }
            }
        }
        array[left] = pivot;
        return left;
    }

    private static void divideAndSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = pivotSort(array, left, right);
        divideAndSort(array, left, i - 1);
        divideAndSort(array, i + 1, right);
    }
}

• 测试代码

public class SortTest {
    public static void main(String[] args) {
        int[] array = new int[] {3,25,88,299,23,88,-1};

        System.out.println(Arrays.toString(ShellSort.sort(array)));
        //System.out.println(Arrays.toString(MergeSort.sort(array)));
        //System.out.println(Arrays.toString(QuickSort.sort(array)));
    }
}

总结

这次的三个排序（希尔，归并，快速）是NlogN平均时间度的算法，可以从通过跳跃式减少完全逆序情况下数据的角度出发考虑时间的减少，我们平时常用的Arrays.sort方法就是使用的快速排序，归并和快速算是平时使用率较高的算法了