c - Gasport 或 Shell Sort 无法正确滑动

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

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

如果您在整个循环中没有交换任何东西，您想更改 gap 值。对于您当前的实现，您可能已经交换了值，例如使用 i=1，但您将在下一个循环中重置 swap=0，因此您将使用相同的 gap 重新迭代，前提是您将值交换为 i 的最后一个值。如果您在 arrDisp 旁边显示 swap 的值，您自己可能已经看到了这个问题。 (我假设 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;
        }
    }
}