RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 1553110
Accepted
Quester
Quester
Asked:2023-11-25 18:20:20 +0000 UTC2023-11-25 18:20:20 +0000 UTC 2023-11-25 18:20:20 +0000 UTC

合并已排序的子数组

  • 772

任务:实现MergeSort

我现在的阶段是:将数组划分为子数组并对这些子数组进行排序

不能:连接已排序的子数组。

条件(这是我的条件,而不是根据任务):如果可能的话,仅使用已经存在的代码(因为我自己弄清楚了如何创建子数组并对它们进行排序,所以我想继续使用它)。

我已经写的代码:

package main

import (
    "fmt"
    "math/rand"
)

func main() {
    // создаю массив под начальные числа и
    // пустой массив под результат сортировки
    var anonsorted, asorted []int
    // заполняю начальный массив псевдорандомными числами.
    for i := 0; i < 20; i++ {
        anonsorted = append(anonsorted, rand.Intn(100))
    }
    asorted = divideAndSort(anonsorted, asorted)
    fmt.Println(asorted)
}

// алгоритм создает группы(под-под-массивы) и сразу сортирует числа внутри этих под-под-массивов
// не могу додуматься как эти группы сотрированных под-под-массивов соеденить.
func divideAndSort(adivided, asorted []int) []int {
    if len(adivided) == 1 {
        return adivided
    }
    divide := len(adivided) / 2
    left := 0
    for i := range adivided {
        if adivided[i] <= adivided[divide] {
            adivided[i], adivided[left] = adivided[left], adivided[i]
            left++
        }
    }
    // отсортированный подмассив от нулевого индекса до его опорного
    oneHalf := divideAndSort(adivided[:divide], asorted)
    // отсортированный подмассив от его опорного индекса до конца массива.
    twoHalf := divideAndSort(adivided[divide:], asorted)
    asorted = merge(oneHalf, twoHalf, asorted)
    return asorted
}

func merge(oneHalf, twoHalf, asorted []int) []int {
    //...
    //asorted = объединение oneHalf и twoHalf
    return asorted
}

更新:

func merge(one, two, sorted []int) []int {
    i, j := 0, 0
    for i < len(one)-1 && j < len(two)-1 {
        if one[i] <= two[j] {
            sorted = append(sorted, one[i])
        } else {
            sorted = append(sorted, two[j])
        }
        i++
        j++
    }
    if i < len(one) {
        sorted = append(sorted, one...)
    }
    if j < len(two) {
        sorted = append(sorted, two...)
    }
    return sorted
}

给出不正确的结果。

更新2:

我发现了所有的错误。

1. перенес инкременты из цикла и условия
2. при выходе из цикла в уловиях сделал заполнение `sorted` 
от того индекса на котором завешился цикл а не от нулеого.
3. цикл сделал до len(array) а не до len(rray)-1

这是最终版本merge()。

func merge(one, two, sorted []int) []int {
    i, j := 0, 0
    for i < len(one) && j < len(two) {
        if one[i] <= two[j] {
            sorted = append(sorted, one[i])
            i++
        } else {
            sorted = append(sorted, two[j])
            j++
        }
    }
    if i < len(one) {
        //здесь была ошибка. Нужно было заполнять от того i
        //на котором закончился цикл а не от нулевого.
        sorted = append(sorted, one[i:]...)
    }
    if j < len(two) {
        //здесь была ошибка. Нужно было заполнять от того j
        //на котором закончился цикл а не от нулевого.
        sorted = append(sorted, two[j:]...)
    }
    return sorted
}
алгоритм
  • 1 1 个回答
  • 43 Views

1 个回答

  • Voted
  1. Best Answer
    MBo
    2023-11-25T20:05:48Z2023-11-25T20:05:48Z
    пока ни один массив не дошел до конца 
       Если очередной элемент первого массива меньше или равен очередному элементу второго
          то записать на выход элемент из первого
      Иначе 
          записать из второго
    
    если первый массив не кончился
        записать всё из него
    если второй массив не кончился
        записать всё из него
    
    • 1

相关问题

  • Golang 中的堆栈实现

  • 二部图中的最大匹配

  • 求两个数的差模为 m 的倍数的算法

  • 如何将平面几何对象表示为矢量以应用于人工神经网络的输入?[关闭]

  • 如何正确执行矩形的 Delaunay 三角剖分?

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    我看不懂措辞

    • 1 个回答
  • Marko Smith

    请求的模块“del”不提供名为“default”的导出

    • 3 个回答
  • Marko Smith

    "!+tab" 在 HTML 的 vs 代码中不起作用

    • 5 个回答
  • Marko Smith

    我正在尝试解决“猜词”的问题。Python

    • 2 个回答
  • Marko Smith

    可以使用哪些命令将当前指针移动到指定的提交而不更改工作目录中的文件?

    • 1 个回答
  • Marko Smith

    Python解析野莓

    • 1 个回答
  • Marko Smith

    问题:“警告:检查最新版本的 pip 时出错。”

    • 2 个回答
  • Marko Smith

    帮助编写一个用值填充变量的循环。解决这个问题

    • 2 个回答
  • Marko Smith

    尽管依赖数组为空,但在渲染上调用了 2 次 useEffect

    • 2 个回答
  • Marko Smith

    数据不通过 Telegram.WebApp.sendData 发送

    • 1 个回答
  • Martin Hope
    Alexandr_TT 2020年新年大赛! 2020-12-20 18:20:21 +0000 UTC
  • Martin Hope
    Alexandr_TT 圣诞树动画 2020-12-23 00:38:08 +0000 UTC
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5