#include <stdio.h>
#include <stdlib.h>

#define TRUE            1
#define FALSE           0
#define OK              1
#define ERROR           0
#define INFEASIBLE        -1
#define OVERFLOW        -2

#define LIST_INIT_SIZE 100

typedef int Status;



/*************SqList***************/
typedef int KeyType;

typedef struct
{
    KeyType key;
}ElemType;

typedef struct
{
    ElemType *elem;
    int length;
    int listsize;
}SqList;

typedef SqList HeapType;

Status InitList_Sq(SqList *L);
void CreateSqList(SqList *L);

/*--------*/
Status InitList_Sq(SqList *L)
{
    L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L->elem)
    {exit(OVERFLOW);}
    L->length = 0;
    L->listsize=LIST_INIT_SIZE;
    return OK;
}

void CreateSqList(SqList *L)
{
    int i,c;
    KeyType k;
   
    printf("How many elements do you want to type in?\n");
    scanf("%d",&c);

    for(i=1;i<=c;i++)/*头元素不用*/
    {
        printf("Please input the %dth key?\n",i);
        scanf("%d",&k);
        L->elem[i].key=k;
        L->length++;
    }
}

void PrintSqList(SqList L)
{
    int i;
    printf("\n");
    for(i=1;i<=L.length;i++)
    {
        printf("%5d",L.elem[i]);
    }
}
/*************End SqList***************/

/*************排序算法***************/

/*----快速排序----*/
int Partion(SqList *L,int low,int high)
{
    KeyType pivotkey;
   
    L->elem[0] = L->elem[low];
    pivotkey = L->elem[low].key;
   
    while(low<high)
    {
        while(low<high && L->elem[high].key>=pivotkey)
        {high--;}
        L->elem[low]=L->elem[high];
        while(low<high && L->elem[low].key<pivotkey)
        {low++;}
        L->elem[high]=L->elem[low];
    }
    L->elem[low] = L->elem[0];
    return low;
}

void QSort(SqList *L, int low, int high)
{
    int pivotloc;
   
    if(low<high)
    {
        pivotloc = Partion(L,low,high);
        QSort(L,low,pivotloc-1);
        QSort(L,pivotloc+1,high);
    }
}

void QuickSort(SqList *L)
{
    QSort(L,1,L->length);
}
/*----堆排序----*/
void HeapAdjust(HeapType *H, int s, int m)
{
    int j;
    ElemType rc;
   
    rc = H->elem[s];
    for(j=2*s;j<=m;j*=2)
    {
        if(j<m && H->elem[j].key < H->elem[j+1].key)
        {j++;}
        if(rc.key >= H->elem[j].key)
        {break;}
        H->elem[s] = H->elem[j];
        s = j;
    }
    H->elem[s] = rc;
}

void HeapSort(HeapType *H)
{
    int i;
    ElemType e;
   
    for(i=H->length/2;i>0;i--)
    {
        HeapAdjust(H,i,H->length);
    }
    for(i=H->length;i>1;i--)
    {
        e = H->elem[1];
        H->elem[1] = H->elem[i];
        H->elem[i] = e;
       
        HeapAdjust(H,1,i-1);
    }
}
/*************END排序算法***************/

/*************主函数***************/
int main()
{
    int choice;
    SqList sl;
   
    clrscr();
   
    InitList_Sq(&sl);
    CreateSqList(&sl);
   
    printf("\nBefore sorting:\n");
    PrintSqList(sl);
   
    for(;;)
    {
        printf("\n*********************\n");
        printf("Please choose the sorting type!\n");
        printf("1.QuickSort\n");
        printf("2.HeapSort\n");
        printf("*********************\n");
        printf("Your choice:");
        scanf("%d",&choice);
   
        if(choice==1)
        {
            QuickSort(&sl);
            break;
        }
        else if(choice==2)
        {
            HeapSort(&sl);
            break;
        }
        else
        {
            printf("No such opion!\n");
            printf("Please choose again!\n");
        }
    }
   
    printf("\nAfter sorting:\n");
    PrintSqList(sl);
   
    getch();
   
    return 0;
}
/*************END主函数***************/