chapter_sorting/merge_sort/

[giscus[bot]]

chapter_sorting/merge_sort/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_sorting/merge_sort/

[zxc1518343069]

你好，想请问一下上述图片是通过什么制作的

[krahets]

哈喽，用 Keynote 哈

[zxc1518343069]

您好，您写的非常棒。还想请问一下有后续迭代的计划吗？ 比如 补充 十大排序中其他的?

[krahets]

@zxc1518343069 感谢鼓励！有的，正在加紧更新中～ 其他排序算法会在将来更新哒

[SMNrootQYS]

写的很棒

[krahets]

谢谢鼓励！

[iron-irax]

感谢大佬，对于菜鸟如我来说真是相见恨晚又恨早。期待后续更新！

[krahets]

谢谢鼓励～会加油更新的！！

[gltianwen]

    public static int[] mergeSorting(int[] nums){
        if (nums.length <= 1) {
            return nums;
        }
        int num = nums.length >> 1;
        int[] left = Arrays.copyOfRange(nums, 0, num);
        int[] right = Arrays.copyOfRange(nums, num, nums.length);
        return merge(mergeSorting(left), mergeSorting(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        int[] result = new int[left.length + right.length];

        while(i < left.length && j < right.length){
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }

        while (i < left.length) {
            result[k++] = left[i++];
        }
        while (j < right.length) {
            result[k++] = right[j++];
        }
        
        return result;
    }

这样会不会更简洁

[krahets]

So clean!

[yy1781051483]

今年实习机考，就是一个归并排序相见恨晚

[yy1781051483]

不会是华为5月份那一批吧，我也是

[krahets]

不会是华为5月份那一批吧，我也是

震惊！我竟回复我自己（doge）

[mao888]

你好，将merge函数里的for循环，里的第三个else合并到第一个 if 里面可以吗，他俩的逻辑和第二个if一样的呀。我尝试之后，panic: runtime error: index out of range [2] with length 2 。
能帮我解答一下吗？
是否能把第三个else合并到第一个，能，麻烦出一下代码，不能的话，恳请指导一下原因。

 // 通过覆盖原数组 nums 来合并左子数组和右子数组
	for k := left; k <= right; k++ {
		// 若“左子数组已全部合并完”或“左子数组元素 > 右子数组元素”，则选取右子数组元素，并且 j++
		if i > leftEnd || tmp[i] > tmp[j] {
			nums[k] = tmp[j]
			j++
			// 否则，若“右子数组已全部合并完”或“左子数组元素 <= 右子数组元素”，则选取左子数组元素，并且 i++
		} else if j > rightEnd || tmp[i] <= tmp[j] {
			nums[k] = tmp[i]
			i++
			// 否则，若“左子数组元素 > 右子数组元素”，则选取右子数组元素，并且 j++
		}
		//else {
		//	nums[k] = tmp[j]
		//	j++
		//}
	}

[krahets]

哈喽，两种写法不是等价的。把条件 3 合并到条件 1 后，当出现 tmp[i] > tmp[j] 时就会直接执行条件 1 ，但是此时可能右子数组已经合并完了（即条件 2 中的 j > rightEnd），这样就出现了越界报错。

[mao888]

感谢，希望佬继续更新后续的排序算法!

[DoubtedYapper71]

问一下后续有动态规划的计划吗？

[krahets]

哈喽～有的，不过比较靠后

[Walhalla-Summary]

最近几天看了很2~3遍，收益匪浅！感想遇见！还望K神开通捐赠通道。

[krahets]

哇 这几天看到的最暖心的评论！谢谢鼓励，捐赠还是算了吧哈哈哈，毕竟是免费的

[zwrong]

清晰的，通过看图一下子明白原理是怎么样的。先看一遍K神的算法图，快速回忆一下算法，然后上课听老师讲效率高

[zwrong]

K神，能够把归并的过程也画个图呢？感觉可以更直观的看出是怎么归并，方便与快速排序比较。
我先自己尝试画一下

[krahets]

HI! 归并排序有图呀，你是说想要更详细的图吗？

[zwrong]

看到了看到了，应该是我浏览器的原因没有显示，不好意思。
图画的很棒，一看就懂

[lethexixin]

链表排序：具体实现细节比较复杂，有兴趣的同学可以查阅相关资料进行学习

[lethexixin]

K神，这个链表排序，有没有比较好的参考链接推荐的呀

[krahets]

Hi, 我以前写过一个相关题解 148. 排序链表

[TDB001]

1 if (i > leftEnd)
2 nums[k] = tmp[j++];
3 // 否则，若“右子数组已全部合并完”或“左子数组元素 <= 右子数组元素”，则选取左子数组元素，并且 i++
4 else if (j > rightEnd || tmp[i] <= tmp[j])
5 nums[k] = tmp[i++];
6 // 否则，若“左右子数组都未全部合并完”且“左子数组元素 > 右子数组元素”，则选取右子数组元素，并且 j++
7 else
8 nums[k] = tmp[j++];

k神第1、2行是否冗余了，删除即可？

[krahets]

Hi 不是冗余的哈，如果去掉了，当 i > leftEnd 成立的时候，也可能进入第 4 行的分支。可以删掉运行下代码看看

[TDB001]

好的，谢谢

[zhgqcn]

K神好，我刷Leetcode 剑指 Offer 51. 数组中的逆序对，用了上述代码，会有部分用例问题，但是不知道错在哪，能否请教下

class Solution {
    int res = 0;
    public int reversePairs(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        mergeSort(nums, left, right);
        return res;
    }

    public void mergeSort(int[] nums, int left, int right){
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    public void merge(int[] nums, int left, int mid, int right){
        int[] tmp = Arrays.copyOfRange(nums, left, right + 1);
        int leftStart = left - left, leftEnd = mid - left;
        int rightStart = mid + 1 - left, rightEnd = right - left;
        int i = leftStart, j = rightStart;
        for(int k = left; k <= right; k++){
            if(i > leftEnd){
                nums[k] = tmp[j++];
            }else if(j > rightEnd || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else{
                System.out.println(mid - i + 1);
                res += mid - i + 1;
                nums[k] = tmp[j++];
            }
        }
    }
}

[zhgqcn]

问题解决

res += mid - left - i + 1;

• 有点隐蔽

[zhuasdfg]

这也太难了吧，那个merge()中的比较 tmp[i] 和 tmp[j] 的大小和i，j的各种操作，我看了好久，画图推了半天才看明白原理，但也就最多做到勉强看懂这么写能得到结果，这代码我只能感叹把指针玩出花来了，泰裤辣！

[krahets]

更新了一版新的实现，现在应该简单一些啦～

[Boiling-water]

k神可以出一篇迭代和递归的算法。其他算法里总是提到这两个算法，看的多了，发现越看越迷糊

[krahets]

确实！

[Boiling-water]

期待哈

[TDB001]

func merge(nums: inout [Int], left: Int, mid: Int, right: Int) {
// 初始化辅助数组
let tmp = Array(nums[left ..< (right + 1)])

[TDB001]

k神，swift这一行写成闭区间就可以把，可以少个加法运算 let tmp = Array(nums[left...right])

[krahets]

只要两个区间是等价的就行～

[lanomw]

merge循环内逻辑不太好理解，变量太多，整理个草图

开始看没看懂循环内的作用，不懂合并时是怎么排序子数组的。画个图就容易理解了👌

[lanomw]

如果评论能够上传图片就好了，我图是别的地方上传了再拉过来的，留个记录🤣

[krahets]

Hi，仔细想了想，当前实现确实有些绕。已在 #888 简化归并排序实现，新版本应该会好理解一些～

[amlei]

太赞啦！🥳

[amlei]

归并排序，结合图11-10 与 算法流程中的 图11-11 结合起来看，同时辅以编译器进行Debug调式就好理解代码的执行过程了

[buynonsense]

图11-11讲解的顺序是①先递归左子数组直到数组里只有一个元素，②并排序，③再去递归右子数组直到数组里只有一个元素，④并排序。⑤最后合起来
我思考，这个顺序如果改成①③②④⑤，是不是也行呢？或者说有什么区别？

[xhxhwdwd]

结合ChatGPT，加上自己测试，提供一个更容易理解的Python版本：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到数组的中间位置
        left_half = arr[:mid]  # 分割数组为左右两半
        right_half = arr[mid:]

        # 递归地对左右两半进行归并排序
        merge_sort(left_half)
        merge_sort(right_half)

        # 归并过程
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 检查左右两半是否有剩余元素未处理
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
        print(arr)

        return arr

[Zhangyu1229]

这个清楚明白多了

[dhonor-dyj]

for j <= right {
tmp[k] = nums[j]
j++
k++
}
想请问一下这块是不是可以去掉呢，因为在arr中【j, right】区间的数据不就是有序的嘛，后面又把tmp临时数组的数据还原在了arr数组中，感觉有点重复操作。

[Phoenix0415]

给大家介绍一个代码可视化工具 Python tutor，非常好用
我基于这个工具，对这页的归并算法做了代码逐步执行的可视化，也加了更详细的注释，链接在此：归并代码逐步执行可视化

[krahets]

泰库拉！感觉可以推广到所有代码～

[Phoenix0415]

新手必备toolkit

[lingkerio]

做cs61a的时候在他们网站的resource用过，没想到用到这里~

[bnufw]

merge函数中 # 将左子数组和右子数组的剩余元素复制到临时数组中
的两个循环实际上只执行一个吧？

[krahets]

是的，因为只有一个剩余

[SwiftBMan]

貌似看懂了😢

[youngxhui]

merge 阶段不就是两个有序数组的合并吗？ leetcode #88

[krahets]

是的，就是合并两个有序数组

[lt421]

启发到我，我还在想合并的时候怎么确保剩余的元素是有序的。

[Harris-peng]

k这个变量看起来没有用，是否可以移除，或者这样是否更好

function mergeSort(nums, start, end) {
  if (start >= end) return;
  const mid = Math.floor((start + end) / 2);
  mergeSort(nums, start, mid);
  mergeSort(nums, mid + 1, end);
  merge(nums, start, mid, end);
  return nums;
}
function merge(nums, start, mid, end) {
  const temp = [];
  let leftIndex = start;
  let midIndex = mid + 1;
  while (leftIndex <= mid && midIndex <= end) {
    if (nums[leftIndex] < nums[midIndex]) {
      temp.push(nums[leftIndex]);
      leftIndex++;
    } else {
      temp.push(nums[midIndex]);
      midIndex++;
    }
  }
  while (leftIndex <= mid) {
    temp.push(nums[leftIndex]);
    leftIndex++;
  }
  while (midIndex <= end) {
    temp.push(nums[midIndex]);
    midIndex++;
  }
  let tempIndex = 0;
  while (tempIndex < temp.length) {
    nums[start + tempIndex] = temp[tempIndex];
    tempIndex++;
  }
}

[krahets]

可以的，如果初始化一个空的 tmp 数组并将元素依次添加进该数组的话，就不用借助 k 变量了。文中使用变量 k 是为了配合预先定义好长度的数组 const tmp = new Array(right - left + 1);

[WuApr]

好像 map reduce

[xxc111111]

hi! 在上面python代码中，为什么左子树两次递归后右子树才开始递归，当数组[0,3]排序完成后又从右子树开始递归，按逻辑来说肯定正确，但从代码中我找不到这样执行的逻辑

[xxc111111]

而且左子树二次递归后先跳过右子树递归，先调用merge函数，代码怎么会实现这种操作

[krahets]

归并排序是一个标准的深度优先搜索过程，可以再看看二叉树遍历章节～

[lieren1922]

while i <= mid && j <= right {
        if nums[i] <= nums[j] {
            tmp[k] = nums[j];     // 应该是 i
            i += 1;
        } else {
            tmp[k] = nums[j];
            j += 1;
        }
        k += 1;
    }

rust代码合并部分有误

[krahets]

谢谢指正！

[HuaWang135608]

写了个非递归的，但是不知道有啥好处😂

    /**
     * 归并排序的非递归方法
     * 时间复杂度: O(n log n)
     * 空间复杂度: O(n)
     * @param arr 待排序的数组
     */
    public static void mergeSortNonRecursive(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int step = 2; // 初始步长为 2, 两个元素做归并
        for (; step < arr.length; step <<= 1) { // 而后 4 元素、8 元素…… 归并
            for (int left = 0; left < arr.length; left +=step) { // 以 step 为步长，归并数组
                int right = left + step - 1; // 右侧区域可能越界
                if (right >= arr.length) {
                    right = arr.length - 1;
                }
                merge(arr, left, (right + left) >> 1, right);
            }
        }
        step >>= 1; // for 循环的最终退出条件是 step >= arr.length
        // 最后，以步长为中点做归并
        merge(arr, 0, step - 1, arr.length - 1);
    }

[williamherry]

ChatGPT提供的Ruby版

def merge_sort(arr)
  return arr if arr.length <= 1

  mid = arr.length / 2
  left_half = merge_sort(arr[0...mid])
  right_half = merge_sort(arr[mid..])

  merge(left_half, right_half)
end

def merge(left, right)
  result = []
  until left.empty? || right.empty?
    if left.first <= right.first
      result << left.shift
    else
      result << right.shift
    end
  end
  result.concat(left).concat(right)
end