Q_7,1

使用插入排序将序列3，1，4，1，5，9，2，6，5排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <math.h>
#include <ctype.h>

void INSERTION_SORT(int A[], int length)
{
    int i, j, tmp;
    for (i = 0; i < length; ++i)
    {
        tmp = A[i];
        for (j = i; j > 0 && A[j - 1] > tmp; --j)
        {
            A[j] = A[j - 1];
        }
        A[j] = tmp;
    }
}

int main()
{
    int A[9] = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    int length = 9;
    INSERTION_SORT(A, length);
    for (int i = 0; i < length; ++i)
        printf("%d ", A[i]);
    return 0;
}

Q_7.2

如果所有的关键字都相等，那么插入排序的运行时间是多少？

通过调试可以知道当所有关键字都相等时，程序不执行下面代码块

for (j = i; j > 0 && A[j - 1] > tmp; --j)
{
    A[j] = A[j - 1];
}

所以插入排序的运行时间此时为$O(n)$。

Q_7.4

写出使用增量{1,3,7}对输入数据9，8，7，6，4，3，2，1运行希尔排序得到的结果

// 使用{1,3,7}作为增量序列

int Increment[3] = {1, 3, 7};

void SHELL_SORT(int A[], int length)
{
    int i, j, k, tmp;
    for (k = 2; k >= 0; --k)
    {
        for (i = Increment[k]; i < length; ++i)
        {
            tmp = A[i];
            for (j = i; j >= Increment[k]; j -= Increment[k])
            {
                if (tmp < A[j - Increment[k]])
                    A[j] = A[j - Increment[k]];
                else
                    break;
            }
            A[j] = tmp;
        }
        for (int i = 0; i < length; ++i)
            printf("%d ", A[i]);
        printf("\n");
    }
}

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