c++ - 交错插入排序函数排序不正确

Question

我有这个函数，它应该使用插入排序交错来为 shell 排序准备一个数组。我正在测试 insertionSortInterleaved() 函数，如下所述:

void insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    int i = 0;
    int j = 0;
    int temp = 0;

    for (i = i + gap; i < numbersSize; i += gap) {
        j = i;
        while (j - gap >= startIndex && numbers[j] < numbers[j - gap]) {
            temp = numbers[j];
            numbers[j] = numbers[j - gap];
            numbers[j - gap] = temp;
            j = j - gap;
        }
    }
}

现在，主要是，我制作了一个数字 1-20 的数组，但按降序排列，然后我让它打印出数组的每个元素。然后我对数组进行了主要的插入排序，排序后再次返回数组。

int main() {
    int numbers[] = { 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

    for (int i = 0; i < 20; i++) {
        cout << numbers[i] << " ";
    }
    cout << endl;

    insertionSortInterleaved(numbers, 20, 1, 5); //numbers being the array, 20 being the amount of numbers being sorted, 1 being the starting index, and 5 being the gap space)
    for (int j = 0; j < 20; j++) {
        cout << numbers[j] << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}

它输出原始数组很好，但在“排序”之后，它按照与第一次相同的顺序输出数组。之前:20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1之后:20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

排序后，数字不应该是升序排列的吗？如果是这样，我做错了什么？任何帮助表示赞赏!谢谢!

Answer 1

在while (j - gap >= startIndex || numbers[j] < numbers[j - gap])使用||运算符(operator)。 index + gap 也会导致越界错误 watch out。为此，我在 for 循环中更改了 i = 0。

void insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    int i = 0;
    int j = 0;
    int temp = 0;

    for (i = 0; i < numbersSize; i += gap) {
        j = i;
        while (j - gap >= startIndex || numbers[j] < numbers[j - gap]) { // changed Here
            temp = numbers[j];
            numbers[j] = numbers[j - gap];
            numbers[j - gap] = temp;
            j = j - gap;
        }
    }
}

int main() {
    int numbers[] = { 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

    for (int i = 0; i < 20; i++) {
        cout << numbers[i] << " ";
    }
    cout << endl;

    insertionSortInterleaved(numbers, 20, 1, 1); //numbers being the array, 20 being the amount of numbers being sorted, 1 being the starting index, and 1 being the gap space)
    for (int j = 0; j < 20; j++) {
        cout << numbers[j] << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}