chapter_sorting/merge_sort/ #61
Replies: 34 comments 46 replies
-
你好,想请问一下上述图片是通过什么制作的 |
Beta Was this translation helpful? Give feedback.
-
感谢大佬,对于菜鸟如我来说真是相见恨晚又恨早。期待后续更新! |
Beta Was this translation helpful? Give feedback.
-
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;
} 这样会不会更简洁 |
Beta Was this translation helpful? Give feedback.
-
今年实习机考,就是一个归并排序 |
Beta Was this translation helpful? Give feedback.
-
你好,将merge函数里的for循环,里的第三个else合并到第一个 if 里面可以吗,他俩的逻辑和第二个if一样的呀。我尝试之后,panic: runtime error: index out of range [2] with length 2 。 // 通过覆盖原数组 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++
//}
} |
Beta Was this translation helpful? Give feedback.
-
问一下后续有动态规划的计划吗? |
Beta Was this translation helpful? Give feedback.
-
最近几天看了很2~3遍,收益匪浅!感想遇见!还望K神开通捐赠通道。 |
Beta Was this translation helpful? Give feedback.
-
清晰的,通过看图一下子明白原理是怎么样的。先看一遍K神的算法图,快速回忆一下算法,然后上课听老师讲效率高 |
Beta Was this translation helpful? Give feedback.
-
链表排序:具体实现细节比较复杂,有兴趣的同学可以查阅相关资料进行学习 |
Beta Was this translation helpful? Give feedback.
-
1 if (i > leftEnd) k神第1、2行是否冗余了,删除即可? |
Beta Was this translation helpful? Give feedback.
-
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++];
}
}
}
} |
Beta Was this translation helpful? Give feedback.
-
这也太难了吧,那个merge()中的比较 tmp[i] 和 tmp[j] 的大小和i,j的各种操作,我看了好久,画图推了半天才看明白原理,但也就最多做到勉强看懂这么写能得到结果,这代码我只能感叹把指针玩出花来了,泰裤辣! |
Beta Was this translation helpful? Give feedback.
-
k神可以出一篇迭代和递归的算法。其他算法里总是提到这两个算法,看的多了,发现越看越迷糊 |
Beta Was this translation helpful? Give feedback.
-
func merge(nums: inout [Int], left: Int, mid: Int, right: Int) { |
Beta Was this translation helpful? Give feedback.
-
开始看没看懂循环内的作用,不懂合并时是怎么排序子数组的。画个图就容易理解了👌 |
Beta Was this translation helpful? Give feedback.
-
归并排序,结合图11-10 与 算法流程中的 |
Beta Was this translation helpful? Give feedback.
-
图11-11讲解的顺序是①先递归左子数组直到数组里只有一个元素,②并排序,③再去递归右子数组直到数组里只有一个元素,④并排序。⑤最后合起来 |
Beta Was this translation helpful? Give feedback.
-
结合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 |
Beta Was this translation helpful? Give feedback.
-
for j <= right { |
Beta Was this translation helpful? Give feedback.
-
给大家介绍一个代码可视化工具 Python tutor,非常好用 |
Beta Was this translation helpful? Give feedback.
-
merge函数中 # 将左子数组和右子数组的剩余元素复制到临时数组中 |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
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++;
}
} |
Beta Was this translation helpful? Give feedback.
-
好像 map reduce |
Beta Was this translation helpful? Give feedback.
-
hi! 在上面python代码中,为什么左子树两次递归后右子树才开始递归,当数组[0,3]排序完成后又从右子树开始递归,按逻辑来说肯定正确,但从代码中我找不到这样执行的逻辑 |
Beta Was this translation helpful? Give feedback.
-
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代码合并部分有误 |
Beta Was this translation helpful? Give feedback.
-
写了个非递归的,但是不知道有啥好处😂 /**
* 归并排序的非递归方法
* 时间复杂度: 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);
} |
Beta Was this translation helpful? Give feedback.
-
ChatGPT提供的Ruby版
|
Beta Was this translation helpful? Give feedback.
-
chapter_sorting/merge_sort/
Your first book to learn Data Structure And Algorithm.
https://www.hello-algo.com/chapter_sorting/merge_sort/
Beta Was this translation helpful? Give feedback.
All reactions