合并排序实现 [英] Merge sort implementation

问题描述

我是C ++的新手，正在尝试开发用于合并排序的代码.我使用大小为5的样本数组对其进行了测试，但是代码给出的答案不正确.我不知道怎么了.这是我的代码:

I am new to c++ and was trying develop a code for merge sort. I tested it with a sample array of size 5 but the answer put out by the code is not right. I can't figure what's going wrong. Here is my code:

#include <iostream>
#include <cstring>
#include <sstream>
#include <fstream>
#include <iomanip>
using namespace std;
void merge(int, int, int, int*);
void merge_sort(int low, int high, int* p){
    int pivot;
    static int i(1);
    if (high>low)
    {
        cout << "calling merge_sort: "<<i<<endl; i++;
        pivot = low + ((high - low)/2);
        cout << pivot << endl;
        merge_sort(low, pivot, p);
        merge_sort(pivot+1, high, p);
        merge(low, pivot, high, p);

    }
}
void merge(int l, int pi, int h,int* arr)
{
            int start = l;
        int mid = pi+1;
        while((start<=pi)&&(mid <=h)){
            if (arr[start] > arr[mid])
            {
                int temp = arr[mid];
                arr[mid] = arr[start];
                arr[start] = temp;
                mid++;
             }
            else
                start++;
    }
}
int main() 
{
    int a[] = {2, 42, 3, 7, 1};
    merge_sort(0, 4, a);
    for (int i = 0; i<=4 ; i++)
        cout << a[i] << endl;
    return (0);

}

输出如下:

calling merge_sort: 1
2
calling merge_sort: 2
1
calling merge_sort: 3
0
calling merge_sort: 4
3
1
3
7
2
42

我已经看到一些用于在stackoverflow上实现合并排序的代码，但是它们使用了另一个我想避免的临时数组.

I have seen some codes for merge sort implementation on stackoverflow but they use another temporary array, which I want to avoid.

在解决此问题方面，我们将不胜感激.

Any help is greatly appreciated in sorting this issue.

推荐答案

合并中的逻辑是错误的.在合并阶段，您知道您有2个部分的已排序数字.比较并交换arr[start]和arr[mid]时，如果arr[start] > arr[mid+1]，则将中断对最前面的一组数字的排序.该示例显示了您的代码有问题，因为2将被放置在错误的位置:

The logic in your merge is wrong. During the merge phase you know that you have 2 sections of sorted numbers. When you compare and swap arr[start] and arr[mid] you will break the sorting of the top set of numbers if arr[start] > arr[mid+1]. The example shows a problem with your code as 2 will be left in the wrong place:

4 6 8 | 1 3 5  ->  1 6 8 | 4 3 5
^       ^          ^         ^

为了使2个部分保持排序，您必须将arr[start]插入顶部数字集的正确位置，这会使复杂性比O(n lg n)差.这就是使用第二个数组的原因.

In order to keep the 2 sections sorted you would have to insert arr[start] in the correct place in the top set of numbers which would make the complexity worse than O(n lg n). This is the reason that a second array is used.

有些方法使用比原始数组小的数组进行合并，这些方法有开销，但不会影响复杂性(或正确性).如果要在位置进行O(n lg n)排序，则可以使用quicksort或heapsort.

There are method which use smaller arrays than the original for merging, these have their overheads but don't compromise the complexity (or correctness). If you want an O(n lg n) in place sort then quicksort or heapsort is the way to go.

这篇关于合并排序实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！