#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int length;
int j=1;//快速排序的趟数；

void clear()
{
    char ch;
    do{ch=getchar();}
    while(ch!='\n');
}
//////////////////////////////////////////////////////////////////////////////
int Partition(int *r, int low, int high)
{
    //printf("第%d趟排序初始位置low:%d\thigh:%d\n",j,low,high);
    int pivotkey;
    pivotkey = r[low]; // 用子表的第一个记录作轴记录
    while (low<high)   // 从表的两端交替地向中间扫描
    {
        while (low<high && r[high]>=pivotkey) --high;
        r[low] =r[high]; // 将比轴记录小的记录换到低端
        while (low<high && r[low]<=pivotkey) ++low;
        r[high] =r[low]; // 将比轴记录大的记录换到高端
    }
    r[low]=r[high]=pivotkey;
    /*printf("第%d趟排序后结果：",j);
    for(int i=1; i<=length; i++)
    {
        printf("%d ",r[i]);
    }
    printf("\n");*/
    //printf("第%d趟排序后位置low:%d\thigh:%d\n",j++,low,high);//轴所在位置low=high=轴
    //printf("********************************************************************************\n");
    return low; // 返回轴所在位置
} // Partition
void QSort(int *r, int low, int high)
{
// 对顺序表L中的子序列L.r[low..high]进行快速排序
    int pivotloc;//轴心的位置
    if (low < high)   // 长度大于1
    {
        pivotloc = Partition(r, low, high); // 将L.r[low..high]一分为二
        //printf("--------------------------------------------------------------------------------");
        //printf("对%d到%d的左子序列排序:\n",low,pivotloc-1);
        QSort(r, low, pivotloc-1); // 对低子表递归排序
        //printf("--------------------------------------------------------------------------------");
        //printf("对%d到%d的右子序列排序:\n",pivotloc+1,high);
        QSort(r, pivotloc+1, high); // 对高子表递归排序
   }
} // QSort
/////////////////////////////////////////////////////////////////////////
void insert_sort(int start,int len,int *r,int length)
{
    int n = length-start+start;
    int tem;
    for (int i=len+start; i<=n; i+=len)//对那一组排序
        for (int j=i; j>len; j-=len)//把r[j]插入到r[1]r[1+len]r[1+2len]r[i-len]中
        {
            if (r[j] < r[j-len])
            {
                tem=r[j];
                r[j]=r[j-len];
                r[j-len]=tem;
            }
            else break;
        }
}
void shell_sort(int *r,int length)
{
    int len,j;
    for(len=length/2; len>0; len/=2)
        for(j=1; j<=len; j++)
            insert_sort(j,len,r,length);
}
//////////////////////////////////////////////////////////////////////
int main()
{
    clock_t start,stop;
    double used_time_1,used_time_2;
    FILE *q;
    system("color f9");
    int a[510001];
    int *r=a;
    int i;
lab_1:
    j=1;//初始化j
    printf("请输入排序个数(<=510000)：");
    scanf("%d",&length);
    //printf("请逐个输入排序数：");
    printf("将随机产生%d个排序数进行shell排序：\n",length);
    for(i=1; i<=length; i++)
    {
        *(r+i)=rand()%100;
        //*(p+i)=*(r+i);
        //scanf("%d",r+i);
        printf("%d\t",r[i]);
    }
    q=fopen("排序数.txt","w+");
    if(!q) exit(-1);
    for(i=1; i<=length; i++)
    {
        fprintf(q,"%d ",r[i]);
        //if(i%10==0)printf("\n");
    }
    fclose(q);
    printf("\n");
    printf("********************************************************************************\n\n\n");
    start=clock();
    shell_sort(r,length);
    stop=clock();
    used_time_1=((double)(stop-start))/CLK_TCK;
    printf("希尔排序后的序列：\n");
    printf("次序数\t排序数\n");
    for(i=1; i<=length; i++)
    {
        printf("%d\t%d\n",i,r[i]);
    }
    printf("\n");
    /////////////////////////////////////////////////////////////////////
    q=fopen("排序数.txt","r");
    if(!q) exit(-1);
    printf("文件打开成功!\n");
    //int b[100];
    printf("将从文件读入%d个排序数进行快速排序：\n",length);
    for(i=1; i<=length; i++)
    {
        fscanf(q,"%d",&r[i]);
        printf("%d\t",r[i]);
        //if(i%10==0)printf("\n");
    }
    printf("\n");
    printf("文件读入成功!\n");
    fclose(q);

    ////////////////////////////////////////////////////////////////////////

    printf("********************************************************************************\n\n\n");
    start=clock();
    int low=1;
    int high=length;
    printf("快速排序过程：\n");
    QSort( r, low, high);
    stop=clock();
    used_time_2=((double)(stop-start))/CLK_TCK;
    printf("快速排序后的序列：\n");
    printf("次序数\t排序数\n");
    for(i=1; i<=length; i++)
    {
        printf("%d\t%d\n",i,r[i]);
    }
    printf("\n");
    printf("shell排序用时%f秒\n",used_time_1);
    printf("快速排序用时%f秒\n",used_time_2);
    printf("继续请按 y：");
    clear();
    char ch=getchar();
    if (ch=='y') goto lab_1;
    return 0;
}