GapSort或ShellSort没有正确地交换

Question

我正在设置一个GapSort程序，因为有些数组代码不起作用。我遗漏了什么？

void main()
{
    int eX[10] = {1, 3, 49, 29, 20, 8, 28, 24, 10, 29};
    int eXlen = sizeof(eX) / sizeof(int);
    gapSort(eX, eXlen);
} 
void gapSort(int arr[], int len)
    {
        int temp, gap, swap;
        gap = len / 2;
        while (1)
        {
            for (int i = 0; i < len - gap; i++)
            {
                swap = 0;
                if (arr[i] > arr[i + gap])
                {
                    temp = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = temp;
                    swap = 1;
                }
            }
            if (swap == 0)
            {
                if (gap == 1)
                    break;
                gap /= 2;
            }
        }
    }

1，3，49，29，20，8，28，24，10，29这类数组不起作用

Answer 1

您必须将swap = 0;放在for循环之前。

如果在整个循环中没有交换任何内容，则需要更改gap值。对于当前的实现，您可能已经交换了值，例如i=1，但是在下一个循环中会重置swap=0，所以只有当您将值替换为i的最后一个值时，才会使用相同的gap重新迭代。如果您将swap的值显示在arrDisp旁边，您可能已经看到了这个问题。(我假设arrDisp是一个显示数组内容的函数。这个函数调用在编辑之前在最初的问题中。)

static void gapSort(int arr[], int len)
{
    int temp, gap, swap;
    gap = len / 2;
    while (1)
    {
        swap = 0;
        for (int i = 0; i < len - gap; i++)
        {
            if (arr[i] > arr[i + gap])
            {
                temp = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = temp;
                swap = 1;
            }
        }
        /* arrDisp(arr, len); */
        if (swap == 0)
        {
            if (gap == 1)
                break;
            gap /= 2;
        }
    }
}