问题引入 

【问题描述】

实现直接插入排序、希尔排序。

【输入形式】

输入2组待排序序列。

【输出形式】

输出分别使用插入排序、希尔排序的排序结果。

【样例输入】

5

7 3 5 0 -9

6

2 4 6 3 4 2

【样例输出】

insertSort:

-9 0 3 5 7

shellSort:

2 2 3 4 4 6

程序设计 

#include
#include
#define MAX 1000
void insertSort(int list[], int n)
{
    int i,j,t;
    for(i=1;i
        t=list[i];
        for(j=i-1;j>=0&&t
            list[j+1]=list[j];
        }
        list[j+1]=t;
    }    
}
void shellSort(int list[], int n,int dk[],int t)
{
    int k;
    for(k=0;k
        shellInsert(list,dk[k],n); 
    }        
}
void shellInsert(int list[],int dk,int n)
{
    int i,j,t;
    for(i=dk;i
        if(list[i]
            t=list[i];
            for(j=i-dk;j>=0&&t
                list[j+dk]=list[j];
            }
            list[j+dk]=t;
        }
    }    
}
void printList(int list[], int n)
{
     int i;
     for(i=0; i      {
         printf("%d ", list[i]);
     }
     printf("\n");
}
int main()
{
   int i,n;
    int a[MAX];
    int dk[10];
    scanf("%d",&n);
    for(i=0;i     {
        scanf("%d",&a[i]);
    }
    printf("insertSort:\n");
    insertSort(a,n);
    printList(a,n);

    scanf("%d",&n);
    for(i=0;i     {
        scanf("%d",&a[i]);
    }
    printf("shellSort:\n");
    dk[0]=5;dk[1]=3;dk[2]=1;
    shellSort(a,n,dk,3);
    printList(a,n);
    return 0;

}