Shell 在 C 中排序未给出要求的结果

Question

我需要在 C 中实现 Shell 排序并使用优化版本（其中间隙首先设置为 array/2 的大小，然后将此数字重复除以 2.2）。问题是答案并不总是完全排序，我不确定这是因为我的代码中的某些逻辑错误还是 Shell 排序的某些缺点。

这是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define MAX 7

void shellSort(int *a, int size);
void insert(int *a, int next_pos, int gap);

void shellSort(int *a,int size)
{
    int gap = floor(size/2);
    int next_pos;
    while (gap>0)
    {
        for(next_pos = gap; next_pos < size; next_pos++)
            insert(a, next_pos, gap);

        if(gap == 2)
            gap = 1;
        else
            gap = (int)(gap/2.2);
    }
}

void insert(int *a, int next_pos, int gap)
{
    int value = a[next_pos];
    while(next_pos >= gap && a[next_pos] < a[next_pos-gap])
    {
        a[next_pos] = a[next_pos-gap];
        next_pos = next_pos - gap;
    }
    a[next_pos] = value;
}

int main()
{
    int nums[MAX];
    time_t t;
    srand((unsigned) time(&t)); // seed randomiser

    printf("Array before sorting:\n");
    int i;
    for(i=0; i<MAX; i++)
    {
        nums[i] = rand() % 101; // filling array with random numbers
        printf("%d\t", nums[i]);
    }

    shellSort(nums, MAX);

    printf("\nArray after sorting:\n");
    for(i=0; i<MAX; i++)
        printf("%d\t", nums[i]);

    return 0;
}

以下是我的输出：

Array before sorting:
74  26  1   12  38  81  94  
Array after sorting:
12  1   26  38  74  81  94

编辑：在我完成问题之前发布哎呀

Answer 1

我认为你的问题出在这里：

 int value = a[next_pos];
 while(next_pos >= gap && a[next_pos] < a[next_pos-gap])

由于您要在下面的行中更改 next_pos，我认为这些行应该读作（如果我对 shellsort 的理解是正确的）：

 int value = a[next_pos];
 while(next_pos >= gap && value < a[next_pos-gap])

Shell 在 C 中排序未给出要求的结果

Shell sort in C not giving required result

c

sorting

shellsort