#include
using namespace std;
void ShellQin(int A[],int n)
{
    int gap=n/2;
    int i,j;
    for(;gap>0;gap=gap/2)//设置初始gap，按照gap进行分组，gap按照gap/2递减
    {
        //设置好gap以后，从gap开始一直到最后一个元素，为每一个元素在其对应的组进行插入排序。gap应该是该组所在位置的第2个元素，第一个元素位置是0
        for(i=gap;iA[j])
            {
                /*如果A[j]>A[j-gap]意味着A[j]大于其所在组的前一个位置，那么将
                  A[j]保存在temp中，将从组中所有大于A[j]的数后移，最后空出来的位置
                  存放A[j]
                */
                int temp=A[j];//保存A[J]
                do
                {
                    A[j]=A[j-gap];
                    j=j-gap;
                }while(j>=0&&temp