主页 / 问题 / 1524166
Accepted
citn
Asked:2023-06-06 09:27:28 +0800 CST2023-06-06 09:27:28 +0800 CST

壳排序算法

  • 772

如何设置步长：h[t]=1, h[m-1]=2h[m+1]；t=log2(n-1)到 Shell 排序算法？我自己尝试过，用不同的步骤获取源代码，替换我自己的，但没有成功。如何设置步骤？

void ShellSort(int* a, size_t n, size_t* bc, size_t* ac, size_t* am) /*шаг задается формулой h[t]=1, h[m-1]=2h[m+1]; t=log2(n-1)*/
{
    const int t = (int)(log2(n-1));
    int i, j, k, m, x;
    /* формирование массива шагов*/
    int* h = (int*)malloc(t * sizeof(int));
    h[t] = 1;
    for (m = t - 2; m >= 0; m--)
        h[m-1] = 2*h[m + 1];
    /*непосредственно сортировка*/
    for (m = 0; m < t; m++)     /*последовательно перебираем все расстояния*/
    {
        k = h[m];
        for (i = k; i < n; i++) /*до конца цикла метод вставки с учетом шага h[m]*/
        {
            x = a[i]; j = i - k;
            while (j >= 0 && x < a[j])
            {
                a[j + k] = a[j];
                j -= k;
            }
            a[j + k] = x;
        }
    }
    free(h);
}
c

1 个回答

  1. Best Answer

    所以（加倍）你可以设置步骤，但这是一个不利的方法，例如，直到最后一步（步骤1）才比较偶数和奇数元素，即 通常会导致二次复杂度。但是，该方法必须有效。

    您在数组大小和最后一步设置上存在不一致 - 在大小为 t 的数组中，最后一个元素的索引为 t-1，并且您设置了第 t 个，而在之前的元素中您有任何东西，并且不使用大小为 1 的步长。修理它

    h[t-1] = 1;

    我还注意到一件事：

    h[m] = 2*h[m + 1];
    • 0

相关问题