c++ - 这是shell排序还是插入排序？

Question

我刚开始学习排序算法并在网上找到了一个。起初我以为这是一个 shell 排序，但它缺少“k”的明显间隔和数组的一半，所以我不确定它是否是。我的第二个猜测是插入排序，但我只是来这里仔细检查一下:

for(n = 1; n < num; n++)
{
    key = A[n];
    k = n;
    while((k > 0) && (A[k-1] > key))
    {
        A[k] = A[k-1];
        k = k-1;    
    }
    A[k] = key;
}

此外，如果您能解释为什么这也会有帮助

Answer 1

Shell Sort由对原始数组的子数组执行的许多插入排序组成。

您提供的代码是插入排序。

要获得 shell 排序，它会粗略地让您的代码周围的其他 for 更改 h(shell 排序中的间隙)和子数组的起始索引在内部，不是从 k 移动到 k-1，而是从 k 移动到 k+h(或 k-h 取决于插入排序的方向)