C - Shell Sort (one of the simplest)-蒲公英云

C - Shell Sort (one of the simplest)

青旅半醒 2022-11-01 10:49 113阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net

/*
 * Shell Sort:
 *
 * The basic idea of this sorting algorithm is that in early stages, far-apart
 * elements are compared, rather than adjacent ones as in simpler interchange sorts.
 * This tends to eliminate large amounts of disorder quickly, so later stages have
 * less work to do. The interval between compared elements is gradually decreased to
 * one, at which point the sort effectively becomes an adjacent interchange method.
 *
 * There are three nested loops. The outermost controls the gap between compared
 * elements, shrinking it from n/2 by a factor of two each pass until it becomes zero.
 * The middle loop steps along the elements. The innermost loop compares each pair of
 * elements that is separated by gap and reverses any that are out of order. Since gap
 * is eventually reduced to one, all elements are eventually ordered correctly.
 * ShellSort.c - by FreeMan
 */
void ShellSort(int v[], int n)
{
    int gap, i, j, temp;
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        for (i = gap; i < n; i++)
        {
            for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
        }
    }
}