algorithm - 带间隙的 Shell 排序和混淆

Question

我最近看到并研究了 shell-sort 算法并看到了提供的示例 here .在示例中，他们考虑“inc”或“gap”。

我做了一个c实现的算法，把gap值作为参数进行排序。

我观察到的事实是，对于 10 个未排序的值，它们是:

5, 1, 3, 2, 4, 8, 6, 9, 7, 10

使用任何间隙，我得到以下输出:

1 2 3 4 5 6 8 7 9 10

我已经构建了代码的递归版本，它在这里:

void shellSort(int *arr, int size, int gap){
    int i, tmp;
    if (gap == 0) return;
    for (i = 0; i < size / gap; i+=gap){
        if (i < size - 1){//Valid Index
            if (arr[i] > arr[i + gap]){
                tmp = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = tmp;
            }
        }
    }
    printf("Interation : \n");
    for (i = 0; i < 10; i++){
        printf("%d\t", arr[i]);
    }
    printf("\n\n");
    shellSort(arr, size, gap - 1);
}

示例:

int main()
{
    int arr[] = { 5, 1, 3, 2, 4, 8, 6, 9, 7, 10 }, i;
    shellSort(&arr[0], 10, 3);
    getch();
    return 0;
}

看了网上的资料后，我对选择这个间隙值完全困惑，在一些地方，比如维基百科，他们使用的是间隙序列。一些帮助将不胜感激。

修正后，

for (i = 0; i < size - gap; i++)

输出:

1 3 2 4 5 6 8 7 9 10

Answer 1

1. 这段代码不是 shell 排序，它是一种 comb sort
2. 在这一行
   for (i = 0; i < size / gap; i+=gap)
   index i 不会遍历整个数组。可能的更正:
   for (i = 0; i < size - gap; i++)
3. 对于完全排序，您必须在发生交换时使用 gap = 1 重复排序。 Examples

每本关于 shellsort 或 combsort 的手册中都描述了差距。简而言之 - 两个由间隙分隔的索引遍历数组，因此无序元素正在靠近它们在排序数组中的位置。每次运行后差距都会减小(在 shellsort 中分母是 2-3，在 combsort 中是 1.3)。将 gap 递减 1(如您的代码所示)会使代码非常慢。