定时实验结果预测

自下而上的方法应该表现得更好：

1. 自上而下的方法递归调用，这将占用 O（logN） 额外的函数调用堆栈空间mergeSortHelper

2. 自上而下的方法需要 O（logN） 额外的时间将数组分解为一个/零个元素

但是它们的空间复杂性都是O（N）（存储排序数据的临时数组）

定时实验结果

自下而上的方法有时比自上而下的方法略好

趋势表明，两种方法的性能之间没有太大差异。

关于为什么两种方法之间的差距不是那么明显的一些个人猜测：

• 我选择的数据点不是最好的演示文稿
• 我的实现不是最佳实践
• 该部分花费了太多时间，以至于它掩盖了故障过程/额外的调用堆栈空间merge
• 编译器在引擎盖下做了一些优化黑魔法

关于测试：

• 测试数据集：随机排列整数数组列表
• 测试数据类型：整数
• 测试数据大小：[0， 10k]，步长：500
• 每个数据点的跟踪数：10000

自上而下/递归合并排序

    /**
     * @return integer overflow prevention mid index getter
     */
    private static int getMiddleIndex(int start, int end) {
        return start + (end - start) / 2;
    }

    /**
     * merge two sorted array into a new sorted array
     */
    private static <T> void merge(ArrayList<T> data, int startLeft, int endLeft, int startRight, int endRight, Comparator<? super T> comparator, ArrayList<T> sortedResults) {
        int leftPointer = startLeft, rightPointer = startRight;
        int index = startLeft;
        while (leftPointer <= endLeft && rightPointer <= endRight) {
            T data1 = data.get(leftPointer);
            T data2 = data.get(rightPointer);
            if (comparator.compare(data1, data2) < 0) {
                sortedResults.set(index, data1);
                leftPointer++;
            } else {
                sortedResults.set(index, data2);
                rightPointer++;
            }
            index++;
        }
        while (leftPointer <= endLeft) {
            sortedResults.set(index, data.get(leftPointer));
            leftPointer++;
            index++;
        }
        while (rightPointer <= endRight) {
            sortedResults.set(index, data.get(rightPointer));
            rightPointer++;
            index++;
        }
        for (int i = startLeft; i <= endRight; i++) {
            data.set(i, sortedResults.get(i));
        }
    }

    /**
     * merge sort, time complexity: O(N*logN), space complexity: O(N)
     */
    private static <T> void mergeSortHelper(ArrayList<T> data, int start, int end, Comparator<? super T> comparator, ArrayList<T> sortedResults) {
        int dataSize = end - start + 1;

        if (dataSize < 2) {
            return;
        }

        int mid = getMiddleIndex(start, end);
        mergeSortHelper(data, start, mid, comparator, sortedResults);
        mergeSortHelper(data, mid + 1, end, comparator, sortedResults);
        merge(data, start, mid, mid + 1, end, comparator, sortedResults);
    }

    /**
     * call mergeSortHelper to do top down merge sort
     */
    public static <T> void topDownMergeSort(ArrayList<T> data, Comparator<? super T> comparator) {
        ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(data.size(), null));
        mergeSortHelper(data, 0, data.size() - 1, comparator, sortedResults);
    }

自下而上/迭代合并排序

    public static <T> void bottomUpMergeSort(ArrayList<T> originalData, Comparator<? super T> comparator) {
        ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(originalData.size(), null));
        for (int sortingRange = 1; sortingRange < originalData.size(); sortingRange *= 2) {
            for (int left = 0; left < originalData.size(); left += 2 * sortingRange) {
                bottomUpMerge(originalData, sortedResults, left, sortingRange, comparator);
            }
            copyArray(sortedResults, originalData);
        }
    }

    private static <T> void bottomUpMerge(ArrayList<T> originalData, ArrayList<T> sortedResults, int start, int sortingRange, Comparator<? super T> comparator) {
        int right = Math.min(start + sortingRange, originalData.size());
        int end = Math.min(start + 2 * sortingRange, originalData.size());
        int leftPointer = start;
        int rightPointer = leftPointer + sortingRange;
        int index = start;
        while (leftPointer < right && rightPointer < end) {
            if (comparator.compare(originalData.get(leftPointer), originalData.get(rightPointer)) <= 0) {
                sortedResults.set(index, originalData.get(leftPointer));
                leftPointer++;
            } else {
                sortedResults.set(index, originalData.get(rightPointer));
                rightPointer++;
            }
            index++;
        }
        while (leftPointer < right) {
            sortedResults.set(index, originalData.get(leftPointer));
            leftPointer++;
            index++;
        }
        while (rightPointer < end) {
            sortedResults.set(index, originalData.get(rightPointer));
            rightPointer++;
            index++;
        }
    }

    /**
     * copy everything in the "from" array into "to" array
     */
    private static <T> void copyArray(ArrayList<T> from, ArrayList<T> to) {
        if (from.size() != to.size()) {
            throw new UnsupportedOperationException("From & to arrays have different sizes!");
        }
        for (int i = 0; i < from.size(); i++) {
            to.set(i, from.get(i));
        }

标签：java,函数,学习,系统,语言,平台,方法,安装, 来源：

本站声明： 1. iCode9 技术分享网（下文简称本站）提供的所有内容，仅供技术学习、探讨和分享； 2. 关于本站的所有留言、评论、转载及引用，纯属内容发起人的个人观点，与本站观点和立场无关； 3. 关于本站的所有言论和文字，纯属内容发起人的个人观点，与本站观点和立场无关； 4. 本站文章均是网友提供，不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属；如您发现该文章侵犯了您的权益，可联系我们第一时间进行删除； 5. 本站为非盈利性的个人网站，所有内容不会用来进行牟利，也不会利用任何形式的广告来间接获益，纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。