自底向上的归并排序的java代码问题

Question

老师你写的对于小组用插入排序优化，您这样写插入排序不是无论数组多大都会执行插入排序么

Answer 1

liuyubobobo 2017-10-19 18:49:17

对的呀，在小数组的情况下先执行插入排序，在数组大小大于15的时候才开始用归并排序。这和自顶向下的逻辑是一致的哦。不管我们的数组有多大，在自顶向下的排序过程中，也是只要分割到<=15个元素的情况下就一定执行插入排序啊：）

要理解对于自顶向下的归并排序一定执行了插入排序，可以尝试在自顶向下的归并排序中相应的位置插入一个输出函数，然后你就会发现，只要你排序的数组大于我们设置的数组长度（在这里是16），就一定执行了插入排序：

private static void sort(Comparable[] arr, int l, int r) {    
    
    if( r - l <= 15 ){    
        // 对于插入排序执行的区间做输出
        System.out.println("Insertion sort in arr[" + l + " , " + r + " ] !");
        InsertionSort.sort(arr, l, r);    
        return;    
    }    
    
    int mid = (l+r)/2;    
    sort(arr, l, mid);    
    sort(arr, mid + 1, r);    
    
    if( arr[mid].compareTo(arr[mid+1]) > 0 )    
        merge(arr, l, mid, r);    
}

另一方面，我们自底向上的归并排序，一上来并没有对整个数组执行插入排序，而是将整个数组分割成若干连续的小数组，对每一个小数组执行了插入排序。注意我们调用的插入排序是有范围参数的。在这里，可以尝试将我们调用插入排序的范围调小，比如下面的代码，我调成了2，然后尝试使用测试用例[8, 7, 6, 5, 4, 3, 2, 1]进行测试：

public static void sort(Comparable[] arr){    
    
    int n = arr.length;    
    
    for( int i = 0 ; i < n ; i += 2 ){  // 注意这里i的步长改成了2
        // 注意，相应的，下面插入排序的调用，r这个参数的计算中，要变为变为i+1  
        InsertionSort.sort(arr, i, Math.min(i+1, n-1) );   
    }    
    
    // 可以尝试在这里输出整个arr看看
    // 对于[8, 7, 6, 5, 4, 3, 2, 1]，此时变为了[7, 8, 5, 6, 3, 4, 1, 2]
    // 也就是连续的每一个长度为2的小数组都被执行了插入排序；
    // 每一个连续的每一个长度为2的小数组都是有序的
    // 但整个数组并不是有序的！
    for(int i = 0 ; i < n ; i ++)
        System.out.println(arr[i]);
    
    // 注意，上面i的步长改成了2，下面的代码，sz也要从2开始！
    for( int sz = 2; sz < n ; sz += sz )    
        for( int i = 0 ; i < n - sz ; i += sz+sz )    
            if( arr[i+sz-1].compareTo(arr[i+sz]) > 0 )    
                merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1) );    

}

总结一下：

在自顶向下的归并排序中，对一个数组，我们不断分割，分割到一定小的长度的时候，也就是来到了“底”，我们开始执行插入排序；

但是在自底向上的归并排序中，我们一上来就要处理“底”，所以一上来，就对连续的小到一定长度的数组执行插入排序，然后再慢慢向上用归并的思路处理更长的数组，直到处理整个数组长度的数组，也就是来到了顶。

• 提问者 busy526 #1

  但是你插入排序的条件是i小于n，这不是会执行全部么，这个插入排序已经全部排序完了啊？

• liuyubobobo 回复 提问者 busy526 #2

  我又进行了一些补充说明，看看你能不能理解？

• 提问者 busy526 回复 liuyubobobo #3

  明白了，我当时在自顶向下的归并排序中就理解有误，谢谢老师

点开查看后面2条评论