外壳排序算法不起作用

Question

我想自己实现外壳排序，而不是复制粘贴到网上，如果有人能帮助我找到错误并改进我愚蠢的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中最常见的错误，请不要为此感到遗憾！

Answer 2

#include <iostream>
#include <cmath>
using namespace std;
void swap(int p, int j, int* arr );
void shellSortwhile(int arr[], int size);
void shellSort(int arr[], int gap,int size);
void print(int* arr, 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=size/2;i>=1;i/=2)#include <iostream>
#include <cmath>
using namespace std;
void swap(int p, int j, int* arr );
void shellSortwhile(int arr[], int size);
void shellSort(int arr[], int gap,int size);
void print(int* arr, int size);
int main() {
    int array[]={12,2,4,23,5,1,6,8,16,64,32,7,43,243,76};
    int size=15;
    print(array,15);
    for (int i=size/2;i>=1;i/=2)
   { shellSort(array,i,size);
    cout<<i<<endl;

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

}
void print(int* arr, int size)
{
    cout<<"Now the array will be printed"<<endl;
    for (int i=0;i<size;i++)
        cout<<arr[i]<<endl;
}
void swap(int p, int j, int* arr )
{
    int temp=arr[p];
    arr[p]=arr[j];
    arr[j]=temp;
}
void shellSortwhile(int arr[], int size) {
    int i, j, gap, temp;
    gap = size/2;

    while(gap > 0) {
        i = gap;

        while(i < size) {
            temp = arr[i];

for(j = i; (j >= gap) && (arr[j - gap] > temp); j -=gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
            i++;
        }
        gap = gap / 2;
    }
}


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

    {
    if (arr[i]>arr[i+gap])
    {
        swap(i,i+gap,arr);

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

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

}
void print(int* arr, int size)
{
    cout<<"Now the array will be printed"<<endl;
    for (int i=0;i<size;i++)
        cout<<arr[i]<<endl;
}
void swap(int p, int j, int* arr )
{
    int temp=arr[p];
    arr[p]=arr[j];
    arr[j]=temp;
}
void shellSortwhile(int arr[], int size) {
    int i, j, gap, temp;
    gap = size/2;

    while(gap > 0) {
        i = gap;

        while(i < size) {
            temp = arr[i];

for(j = i; (j >= gap) && (arr[j - gap] > temp); j -=gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
            i++;
        }
        gap = gap / 2;
    }
}


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

    {
    if (arr[i]>arr[i+gap])
    {
        swap(i,i+gap,arr);
        print(arr,size);

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