归并排序自底向上的Java版本代码疑似有误

Question

老师您好，我看了您的归并排序自底向上的Java版本代码，运行以后，打印数组出来，发现打印出来的数组不是有序的，我怀疑是您的代码有问题，您有时间可以看一下吗？是经过优化的那里

//        // Merge Sort Bottom Up 优化
//        // 对于小数组, 使用插入排序优化
        for (int i = 0; i < n; i += 16)
            InsertionSort.sort(arr, i, Math.min(i + 15, n - 1));

        for (int sz = 16; sz < n; sz += sz)
            for (int i = 0; i < n - sz; i += sz + sz)
                // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
                if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0)
                    merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));

Answer 1

liuyubobobo 2017-11-25 18:38:26

请确定你实验的代码和我github上的代码一致：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(Java)/04-Merge-Sort-Bottom-Up/src/bobo/algo/MergeSortBU.java

我刚才跑了10万组测试用例，没有问题。如果确认和我的代码一致的话，能否给我一组在我的代码下运行会出错误的测试用例？谢谢！

• qq_红_14 #1

  java的代码确实是有误的，
  for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--){
                  arr[j] = arr[j-1];
  }
  这个地方的代码不应该是j>0，所以执行完，是错误的数据

• liuyubobobo 回复 qq_红_14 #2

  我不确定慕课网上的代码是不是版本比较老有bug，课程的代码请以官方github为准。我又测试了一下这一小节的代码，根据我的测试没有问题。如果你确定我的代码有误，请给出一组我的代码会出错误的测试用例？或者直接在github上提issue做修改？谢谢！对于你给出的j>0，由于要保障后面的arr[j-1]中j-1不越界，所以要保证j>0，每次在插入排序中比较的是arr[j]和arr[j-1]两个元素。本小节代码官方github地址：https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/03-Sorting-Advance/Course%20Code%20(Java)/04-Merge-Sort-Bottom-Up/src/bobo/algo

• qq_红_14 回复 liuyubobobo #3

  是这样的老师，我看了慕课网上的代码还有github的代码。在插入排序的方法里面，慕课网的代码是j>0，执行完了，是错误的数据的。github的代码是j>l，执行完了，是正确的数据。
  
  具体代码如下：    // 对arr[l...r]的区间使用InsertionSort排序
      public static void sort(Comparable[] arr, int l, int r){
  
          assert l >= 0 && l <= r && r < arr.length;
  
          for( int i = l + 1 ; i <= r ; i ++ ){
              Comparable e = arr[i];
              int j = i;
              for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--)
                  arr[j] = arr[j-1];
              arr[j] = e;
          }
      }

点开查看后面1条评论