C++：合并和插入排序混合

Question

我一直试图在c++中创建一个合并和插入排序混合。但是，每当我按照确切的顺序在算法中输入这些数字，9,1,1,4,4,0,3,8,5,7,9,5,9,1,3,3,1,5,7,0,7,2(顺便说一句，这是22个数字)，我就得到：1,1,0,1,1,0,2,3,3,3,4,4,5,5,5,7,7,7,8,9,9,9，它显然没有正确排序。

如果你想知道我的算法中是否有错误，答案是否定的。我用相同的顺序分别测试了合并和插入排序算法，每个算法都产生了正确排序的数字数组。

因此，为了将这两种算法结合在一起，该算法可能在其他代码中出错了。(我还修改了插入排序代码，以使其更高效，但这也不是问题，以防您感到奇怪。在我更改算法之前和之后，两个测试都产生了相同的结果:错误的结果。)

这是我的代码，如果你想看的话：

#include <iostream>

void sort (int *array, int low, int mid, int high) {
    //Insertion sort
    for (int i = mid; i < high; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (array[i] < array [j]) {
                int holder = array[j];
                array[j] = array[i];
                array[i] = holder;
                i--;
            }
        }
    }
}
void merge (int *array, int *sub, int low, int mid, int high) {
    //Merge part of mergesort
    int a = low;
    int b = low;
    int c = mid;

    while ((a < mid) && (c < high)) {
        if (array[a] <= array[c]) {
            sub[b] = array[a];
            a++;
        } else {
            sub[b] = array[c];
            c++;
        }
        b++;
    }
    while (a == mid && c < high) {
        sub[b] = array[c];
        c++;
        b++;
    }
    while (c == high && a < mid) {
        sub[b] = array[a];
        a++;
        b++;
    }
    for (int d = low; d < high; d++) {
        array[d] = sub[d];
    }
}
void split (int *array, int *sub, int low, int high) {
    //Split part of mergesort
    if (low < high - 1) {
        int mid = (low + high) / 2;
        split(array, sub, low, mid);
        split(array, sub, mid, high);
        if ((high - low) > 10){
            merge(array, sub, low, mid, high);
        } else {
            sort(array, low, mid, high);
        }

    }
}

int main()
{
    std::cout << "This is a program that sorts integers.\n";
    std::cout << "How many numbers would you like to sort?\n";
    int num;
    std::cin >> num;
    if (num < 0) {
        std::cout << "Invalid amount of numbers.\n";
        return 0;
    } else if (num == 0) {
        std::cout << "No numbers to sort.\n";
        return 0;
    } else if (num == 1) {
        std::cout << "Please type in the number.\n";
        std::cin >> num;
        std::cout << "Your sorted number is: " << num << ".\n";
        return 0;
    }
    int * array = new int [num];
    int * sub = new int [num];
    std::cout << "Please type in the numbers.\n";
    for (int i = 0; i < num; i++) {
        std::cin >> array[i];
    }
    split(array, sub, 0, num);
    std::cout << "Your sorted numbers are: ";
    for (int i = 0; i < num; i++) {
        std::cout << array[i];
        if (i != num - 1) {
            std::cout << ", ";
        } else {
            std::cout << ".\n";
        }
    }
    delete[] array;
    delete[] sub;

    return 0;

}

如果能在这方面提供任何帮助，我们将不胜感激。提前谢谢。

Answer 1

在sort()例程中有两个问题--您只是从mid排序到high (而不是low到high)，使事情半途而废。一旦修复了这个问题，您就需要在j移动到low以下时停止它，而不是0，因为我们并不总是从数组的开始就开始工作。

最后，该函数不再需要mid。

void sort (int *array, int low, int high) {
    //Insertion sort
    for (int i = low; i < high; i++) {
        for (int j = i - 1; j >= low; j--) {
            if (array[i] < array [j]) {
                int holder = array[j];
                array[j] = array[i];
                array[i] = holder;
                i--;
            }
        }
    }
}

稍后，在split()中，调整调用：

sort(array, low, high);

工作示例：https://ideone.com/B1UtSK