问题：

我的Mergesort怎么了？

谷梁楚青

2023-03-14

#include <cstring>
#include <stdint.h>
#include <algorithm>
#include <ctime>
#include <iostream>
#include <cstdlib>


using namespace std;

int array[1000];
int temp[1000];

void mergeSort(int start, int count) {
    if(count == 1) {
        return;
    }
    int startFirst = start;
    int countFirst = count/2;
    int startSecond = startFirst + countFirst;
    int countSecond = count - countFirst;
    mergeSort(startFirst, countFirst);
    mergeSort(startSecond, countSecond);        
    int refFirst = 0;
    int refSecond = 0;
    for(int i = start; i < start + count; i++){
        if(refFirst == countFirst || array[startSecond + refSecond] < array[startFirst + refFirst]) {
            temp[i] = array[startSecond + refSecond];
            refSecond++;
        } else {
            temp[i] = array[startFirst + refFirst];
            refFirst++;
        }
    }
    memcpy(array + start, temp + start, count*sizeof(int));
}

int main() {
    for(int i = 0; i <1000; i++){
        array[i] = 1000 - i;
    }
    mergeSort(0, 1000);
    for(int i =0; i <1000; ++i){
        cout << array[i] << " ";
    }
    cout << endl;
    return 0;
}

我使用两个数组编写了一个简单的MergeSort实现，它输出垃圾：

1 2 3 2 5 4 4 3 9 8 8 7 8 7 6 5 17 16 16 15 16 15 14 13 16 15 14 13 12 11 10 9 33 32 31 32 31 30 29 32 31 30 29 28 27 26 25 25 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 64 63 63 62 62 62 61 60 60 59 58 57 56 63 62 62 61 60 60 59 58 57 56 63 62 61 60 59 58 57 56 56 55 54 53 52 51 50 49 63 62 61 60 5957 56 55 54 53 52 51 50 49 48 46 46 45 44 43 42 41 40 39 38 37 36 35 34 126 125 125 124 124 123 122 121 120 119 118 117 116 115 114 113 111 110 110 125 124 123 122 121 120 119 118 117 116 115 114 113 111 111 110 109 108 107 106 105 104 103 103 102 101 100 99 98 97 96 95 125 124 123 123 122 121 120 119 117113 112 111 110 109 108 107 106105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 86 85 84 82 80 79 78 77 71 70 69 68 65 64 251 250 250 249 249 249 249 249 249 249 248 247 246 249 249 249 249 249 249 246 246 246 246 246 246 246 246 244 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242232 231 230 229 228 227 226 225 223 222 221 220 250 249 247 246 245 243 242 242 242 242 232 229 228 227 226 225 228 228 228 226 226 222 222 222 222 222 222 222 222 219 217 216 212 212 211 210 209 208 207 207 207 207 207 207 207 207 207 207 206 208 208 207 207 206 244 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 199 199 197 199 198 192 199 198 192225 224 223 222 221 220 219 218 217 217 216 215 214 213 212 212 211 210 209 208 207 206 206 206 206 194 192 187 186 188 182 182 182 182 182 182 182 182 182 182 182 182 182 172 182 182 172 182 172 172 182 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 168 168 167 167 167 166 166 156 155 155 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 162 162 162 162 1621 2 3 2 5 4 4 3 9 8 8 7 8 7 6 5 17 16 16 15 16 15 14 13 16 15 14 13 12 11 10 9 33 32 31 32 31 30 29 32 31 30 29 28 27 26 25 25 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 64 63 63 62 62 62 61 60 60 59 58 57 56 63 62 62 61 60 60 59 58 57 56 63 62 61 60 59 58 57 56 56 55 54 53 52 51 50 49 63 62 61 60 5957 56 55 54 53 52 51 50 49 48 46 46 45 44 43 42 41 40 39 38 37 36 35 34 126 125 125 124 124 123 122 121 120 119 118 117 116 115 114 113 111 110 110 125 124 123 122 121 120 119 118 117 116 115 114 113 111 111 110 109 108 107 106 105 104 103 103 102 101 100 99 98 97 96 95 125 124 123 123 122 121 120 119 117113 112 111 110 109 108 107 106105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 86 85 84 82 80 79 78 77 71 70 69 68 65 64 251 250 250 249 249 249 249 249 249 249 248 247 246 249 249 249 249 249 249 246 246 246 246 246 246 246 246 244 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242232 231 230 229 228 227 226 225 223 222 221 220 250 249 247 246 245 243 242 242 242 242 232 229 228 227 226 225 228 228 228 226 226 222 222 222 222 222 222 222 222 219 217 216 212 212 211 210 209 208 207 207 207 207 207 207 207 207 207 207 206 208 208 207 207 206 244 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 242 199 199 197 199 198 192 199 198 192225 224 223 222 221 220 219 218 217 217 216 215 214 213 212 212 211 210 209 208 207 206 206 206 206 194 192 187 186 188 182 182 182 182 182 182 182 182 182 182 182 182 182 172 182 182 172 182 172 172 182 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 168 168 167 167 167 166 166 156 155 155 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 162 162 162 162 162

共有1个答案

刘泰

2023-03-14

在合并数组时，只应在第二个数组未耗尽时从该数组写入。您应该将数组[startSecond+refSecond] 替换为 (refSecond！=countSecond&&数组[startSecond+refSecond]

类似资料：

我的golang代码怎么了？

问题内容：这是我的整个源代码：代码卡在了 fmt.Println（“ enq =”，t）上，但是我不知道为什么，这太奇怪了。问题答案： deQueue在失败情况下无限循环，这阻塞了CPU。Goroutine在执行CPU工作时不会屈服。GOMAXPROCS必须大于等于2才能获得CPU并行性。只是为了踢，这是使用高阶通道的线程安全，无阻塞队列实现：https : //gist.github.
我的for循环怎么了？

我有两个循环。在第一个循环中，我分割字段（分割）。在第二个循环中，我想打印新的字段值。只有0。我想知道循环有什么问题。我没有发现错误。：）我认为问题出在这方面：我在Windows 7中使用Visual Studio 2013编程。 %lf输出（正确）： %f输出（不正确）：
我怎么清洁docker？

通过docker system prune-a清理但只清除了9GB
1.2 怎么打印我的地图

我们提供您的业务地图高清图片的生成服务，每次生成高清地图，1500元起价。并根据打印的范围、详细程度、标注数量来计算实际价格，范围越大、内容越详细、标注越多，价格则越高。以下样图生成价格为2500元：点此下载原图 (约10M，建议在wifi环境下下载) 打印的范围，添加一个区域用以标明输出的范围。地图的详细程度，用地图左下角的比例尺数字告诉小图，如下图所示：有的小伙伴会问，我的地图，打印出来
11.6.1 怎么搜索我的数据？

在地图主界面的右上角有一个搜索的图标，点击即可进入搜索搜索框中输入关键字点击搜索，搜索结果会展现本地数据与在线数据，本地数据：就是自己标注在地图上的数据在线数据：就是公共的POI数据，也可以保存为自己的数据
MergeSort变体的差异？

我正在上大学数据结构课程当涉及到普通的MergeSort和自上而下的MergeSort时 - 有什么区别？到目前为止，我所读到的内容使我相信： “正常”MergeSort只是将已经排序的数组/文件拆分为两半，并将其放入辅助数组中。然后我们开始通过连续比较左边的元素和右边的元素来检查辅助数组，将这些元素按排序顺序写入原始数组。自上而下的MergeSort递归地将一个未排序的数组拆分为更小的部分，

我的Mergesort怎么了？

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档