3月 11 2020
0

到目前看完了选择排序, 插入排序(希尔排序), 冒泡排序, 这些都是遍历加遍历, 复杂度都是n平方级别的, 希尔排序稍微好一些.

现在来看看更快的排序, 这些排序或多或少都采取了不断二分的分治法策略, 所以时间复杂度都要比之前平方级别的

来看看这些更快的方法, 首先是归并排序.

  1. 归并排序的思想
  2. 递归版本的核心方法编写

归并排序的思想

归并排序的核心思想是:

  1. 将要排序的数组分成两部分, 对每一部分按相同的顺序排序
  2. 创建一个等于原来数组的总长度的新数组
  3. 对已经有序的两个子数组, 从两个子数组的开头比较两个子数组的所有元素, 哪个符合顺序(大于或者小于另外一个), 就把哪个元素放入到新的数组中. 直到一个数组的元素全部放入新数组中.
  4. 再把另外一个数组剩余的元素全部放入新数组中. 得到的新数组就是有序的.

很显然, 这个用递归的思路非常容易编写. 用迭代倒不是那么容易. 递归的思路很简单, 主要要写一个将两个有序数组合并成一个的方法.

不过这里还有一个问题要解决, 就是如果每次都创建一个新数组并且返回, 就会反复创建很多数组, 由于只需要创建一个新数组, 所以就创建一个长度和原来数组相同的数组, 然后每次都用这个数组的一部分做临时数组即可.

再考虑到以面向对象的方法编写, 因此还需要一个辅助方法, 即创建一个新数组供其他方法使用. 这样一共需要两个工具方法和一个排序方法:

  1. private static <T extends Comparable<? super T>> void sort(T[] array, int startIndex, int endIndex, boolean reverse), 这个是和之前的排序类一样的核心私有排序方法, 内部使用其他方法.
  2. private static <T extends Comparable<? super T>> void sort(T[] array, int startIndex, int endIndex, T[] tempArray, boolean reverse), 这个方法是实际执行排序的方法, 多一个临时数组参数, 方便反复使用同一个临时数组.
  3. private static <T extends Comparable<? super T>> T[] merge(T[] array1, int array1StartIndex, int array1EndIndex, T[] array2, int array2StartIndex, int array2EndIndex, T[] tempArray), 这是将两个有序数组归并排序到一个临时数组上的对应位置的方法.
  4. private static <T extends Comparable<? super T>> T[] getTempArray(), 这是新创建临时数组的方法.

由于需要在方法中间共用同一个临时数组, 而对外暴露的核心私有方法并没有临时数组参数, 所以需要在核心私有方法中创建一个临时数组变量, 然后套一层上边的第二个方法, 来让其中的各个递归使用相同的临时数组.

核心方法编写

按照方法逻辑来看一层一层看, 首先是最外层的私有核心方法:

private static <T extends Comparable<? super T>> void sort(T[] array, int startIndex, int endIndex, boolean reverse) {
    //先创建一个临时的数组
    T[] tempArray = getTempArray(array.length);

    //交给其他私有方法进行使用, 保证只使用同一个临时数组
    sort(array, startIndex, endIndex, tempArray, reverse);
}

然后看这个使用临时数组的sort()方法, 这个方法是递归的思路所在:

private static <T extends Comparable<? super T>> void sort(T[] array, int startIndex, int endIndex, T[] tempArray, boolean reverse) {

    checkArguments(array, startIndex, endIndex);

    //停机条件是数组只有一项, 直接停止

    //两个索引不相等, 就归并
    if (startIndex != endIndex) {
        sort(array, startIndex, (startIndex + endIndex) / 2, reverse);
        sort(array, (startIndex + endIndex) / 2 + 1, endIndex, reverse);
        merge(array, startIndex, (startIndex + endIndex) / 2, (startIndex + endIndex) / 2 + 1, endIndex, tempArray, reverse);

    }
}

如果数字只有一项, 就停机. 如果数组超过一项, 用中间索引将其分成两半, 对每一半进行排序, 然后按照索引把排好序的两半数组归并起来.

之后看归并方法merge(), 这个方法是核心:

private static <T extends Comparable<? super T>> void merge(T[] array, int array1StartIndex, int array1EndIndex, int array2StartIndex, int array2EndIndex, T[] tempArray, boolean reverse) {

    //记录临时数组的起始索引, 由于后边归并的时候会更新两个数组各自的startIndex, 所以先要保存一个最小的索引
    int tempArrayRangeStart = array1StartIndex;

    //获取临时数组的当前索引, 一开始等于第一个数组的起始索引, 后边会变动.
    int startIndex = array1StartIndex;
    //先遍历数组1的元素, 只要小于, 根据reverse判断是否升序

    //只要两个数组有任意一个被遍历完就结束循环, 否则一直循环
    while (array1StartIndex <= array1EndIndex && array2StartIndex <= array2EndIndex) {

        //在每次循环中不断比较两个数组的第一个元素, 哪个数组的第一个元素小, 就将那个元素放入临时数组, 然后将那个数组的当前索引和临时数组的当前索引都更新

        //升序排列, 谁小先把谁放进temp中
        if (!reverse) {
            //假如第一个数组的第一个元素小于第二个数组的第一个元素
            if (array[array1StartIndex].compareTo(array[array2StartIndex]) < 0) {
                //将其放入临时数组中
                tempArray[startIndex] = array[array1StartIndex];
                //自增临时数组的当前索引和第一个数组的当前索引
                startIndex++;
                array1StartIndex++;
            //如果不大于, 就把数组二的第一个元素放入临时数组, 自增数组二的当前索引和临时数组的当前索引
            } else {
                tempArray[startIndex] = array[array2StartIndex];
                startIndex++;
                array2StartIndex++;
            }
        //降序的思路和前边完全一样
        } else {
            if (array[array1StartIndex].compareTo(array[array2StartIndex]) > 0) {
                tempArray[startIndex] = array[array1StartIndex];
                startIndex++;
                array1StartIndex++;
            } else {
                tempArray[startIndex] = array[array2StartIndex];
                startIndex++;
                array2StartIndex++;
            }
        }
    }

    //执行到这里, 两个数组中一定有一个数组已经被遍历完, 把没有遍历完的数组中剩余元素挨个放入临时数组中

    //如果数组一没有被遍历完, 将剩余部分复制到临时数组中
    if (array1StartIndex <= array1EndIndex) {
        for (int i = array1StartIndex; i <= array1EndIndex; i++) {
            tempArray[startIndex] = array[i];
            startIndex++;
        }
    }

    //如果数组二没有被遍历完, 将剩余部分复制到临时数组中
    if (array2StartIndex <= array2EndIndex) {
        for (int i = array2StartIndex; i <= array2EndIndex; i++) {
            tempArray[startIndex] = array[i];
            startIndex++;
        }
    }

    //最后将临时数组的部分复制到原始数组中, 数组末尾一定是array2EndIndex, 而起始索引我们保存好了, 这样array的对应索引的部分就被归并排序好了.
    for (int j = tempArrayRangeStart; j <= array2EndIndex; j++) {
        array[j] = tempArray[j];
    }

}

最后是创建临时数组的方法, 这个方法有点意思, 由于数组协变, 不能直接创建泛型类型的数组, 这里有个小技巧, 由于T必定实现Comparable<T的父类>, 所以可以用一个套路:

@SuppressWarnings("unchecked")
private static <T extends Comparable<? super T>> T[] getTempArray(int length) {
    return (T[]) new Comparable<?>[length];
}

如果用Object[], 是无法直接转型的, 因为Object[]并没有实现Comparable接口, 但是用Comparable是可以的, 因为T实现了这个接口.

关于泛型数组, 还真的要好好看看.

迭代版本的归并排序, 思路是从数组的开头, 先两两归并, 再四四归并, 再这样一路下去. 书上的练习还要求不能使用额外的临时数组, 待我仔细想想怎么做.

发表于数据结构与算法

发表评论

邮箱地址不会被公开。 必填项已用*标注