教学目的： 掌握简单插入排序、快速排序、堆排序的算法并加以应用。

教学重点：

教学难点：

授课内容：

逆风编程精品
实现下述三种算法，并用以下无序序列加以验证：

49，38，65，97，76，13，27，49

一、简单插入排序

二、快速排序

三、堆排序

以上算法的C源程序。

#define MAXSIZE 20

#define LT(a,b) ((a)<(b))

typedef int KeyType;

typedef int InfoType;

typedef struct{

  KeyType key;

  InfoType otherinfo;

}RedType;

typedef struct{

  RedType r[MAXSIZE 1];

  int length;

}SqList;



void InsertSort(SqList *L)

{

  int i,j;

  for(i=2;i<=L->length;  i)

    if(LT(L->r[i].key,L->r[i-1].key)){

      L->r[0]=L->r[i];

      for(j=i-1; LT(L->r[0].key,L->r[j].key); --j)

	L->r[j 1]=L->r[j];

      L->r[j 1]=L->r[0];

    }

}



void BInsertSort(SqList *L)

{

  int i,j;

  int low,high,m;

  for(i=2;i<=L->length;  i){

    L->r[0]=L->r[i];

    low=1;high=i-1;

    while(low<=high){

      m=(low high)/2;

      if (LT(L->r[0].key,L->r[m].key))

	high=m-1;

      else low=m 1;

    }

    for(j=i-1;j>=high 1;--j)

      L->r[j 1]=L->r[j];

    L->r[high 1]=L->r[0];

  }

}



/* QuickSort related function */

int Partition(SqList *L,int low,int high)

{

  int pivotkey;

  L->r[0]=L->r[low];

  pivotkey=L->r[low].key;

  while(low<high){

    while(low<high&&L->r[high].key>=pivotkey) --high;

    L->r[low]=L->r[high];

    while(low<high&&L->r[low].key<=pivotkey)   low;

    L->r[high]=L->r[low];

  }

  L->r[low]=L->r[0];

  return low;

}

void QSort(SqList *L,int low,int high)

{

  int pivotloc;

  if(low<high){

    pivotloc=Partition(L,low,high);

    QSort(L,low,pivotloc-1);

    QSort(L,pivotloc 1,high);

  }

}

void QuickSort(SqList *L)

{

  QSort(L,1,L->length);

}                    /* End QuickSort related function*/



/*SelectSort related function */

int SelectMinKey(SqList L,int i)

{

  int k;

  int j;

  k=i;

  for(j=i;j<L.length 1;j  )

    if(L.r[k].key>L.r[j].key)

      k=j;

  return k;

}

void SelectSort(SqList *L)

{

  RedType t;

  int i,j;

  for(i=1;i<L->length;  i){

    j=SelectMinKey(*L,i);

    if(i!=j) {

      t=L->r[i];

      L->r[i]=L->r[j];

      L->r[j]=t;

    }

  }

}           /*End SelectSort related function */





typedef SqList HeapType;

void HeapAdjust(HeapType *H,int s,int m)

{

  RedType rc;

  int j;

  rc=H->r[s];

  for(j=2*s;j<=m;j*=2){

    if(j<m&&LT(H->r[j].key,H->r[j 1].key))   j;

    if(!LT(rc.key,H->r[j].key)) break;

    H->r[s]=H->r[j];

    s=j;

  }

  H->r[s]=rc;

}

void HeapSort(HeapType *H)

{

  RedType t;

  int i;

  for(i=H->length/2;i>0;--i)

    HeapAdjust(H,i,H->length);

  for(i=H->length;i>1;--i){

    t=H->r[1];

    H->r[1]=H->r[i];

    H->r[i]=t;

    HeapAdjust(H,1,i-1);

  }

}



main()

{

  int a[]={49,38,65,97,76,13,27,49};

  int i,k;

  SqList s;

  printf("\nThe record to be sort:\n");

  for(i=1;i<9;i  )

    {

      s.r[i].key=a[i-1];

      printf("%d  ",a[i-1]);

    }

  s.length=i-1;

  printf("\n\t1,InsertSort\n\t2,BInsertSort\n\t3,QuickSort\n\t4,SelectSort\n");

  printf("\t5,HeapSort\n\tPress 1..5 to select a function\n");

  scanf("%d",&k);

  switch(k){

    case 1:

      InsertSort(&s);

      break;

    case 2:

      BInsertSort(&s);

      break;

    case 3:

      QuickSort(&s);

      break;

    case 4:

      SelectSort(&s);

      break;

    case 5:

      HeapSort(&s);

      break;

    default:printf("No function which you select.\n");

  }

  printf("\nThe records be sorted:\n");

  for(i=1;i<9;i  )

    printf("%d  ",s.r[i].key);

  printf("\n\n\tPress any key to exit.\n");

  getch();

}