c++ - shellsort 算法不起作用

Question

我想自己实现 shellsort 而不是在线复制粘贴那些，如果有人能帮助我找到错误并改进我愚蠢的 lil 代码，我将不胜感激我会把我的代码放在下面

#include <iostream>
#include <cmath>

using namespace std;

void swap(int p, int j, int *arr);
void shellSort(int arr[], int gap, int size);

int main() {
    int array[] = {12, 2, 4, 23, 5, 1, 6, 8, 16, 64, 32, 7, 43, 243, 76};
    int size = 15;
    for (int i = 15; i >= 1; i /= 2) {
        shellSort(array,i,size);
        cout << i << endl;
    }

    print(array, 15);
    // shellSortwhile(array, 15);
    print(array, 15);
}

void shellSort(int arr[], int gap, int size) {
    for (int i = 0; i < size; i += gap) {
        if (arr[i] > arr[i + gap]) {
            swap(i, i + gap, arr);
            for(int j = i; j >= 0; j -= gap) {
                if (arr[j] < arr[j - gap]) {
                    swap(j-gap, j, arr);
                }
            }
        }
    }
}

我的输出是:

Now the array will be printed
2
4
5
6
7
7
8
1076814756
12
15
16
23
32
43
64

Answer 1

你正在读/写越界。 i+gap 在您的第一次迭代中为 15。您的数组中只有 15 个元素，因此您读取的是最后一个元素之后的一个。这是 C 中最常见的错误，不要为此难过!