實驗八 排序實驗

style="WIDTH: 89.81%; HEIGHT: 64px" src="http://pagead2.googlesyndication.com/pagead/ads?client=ca-pub-4577827332549849&dt=1192819750500&lmt=1192819750&prev_fmts=468x60_as&format=468x15_0ads_al_s&output=html&correlator=1192819750437&channel=1741427766&pv_ch=1741427766%2B&url=http%3A%2F%2Fyzkzoo.5d6d.com%2Fthread-68-1-1.html&color_bg=FFFFFF&color_text=000000&color_link=0000FF&color_url=008000&color_>

style="WIDTH: 82.23%; HEIGHT: 74px" src="http://pagead2.googlesyndication.com/pagead/ads?client=ca-pub-4577827332549849&dt=1192818497343&lmt=1192818497&format=468x60_as&output=html&correlator=1192818497343&channel=1741427766&url=http%3A%2F%2Fyzkzoo.5d6d.com%2Fthread-68-1-1.html&color_bg=FFFFFF&color_text=000000&color_link=0000FF&color_url=008000&color_>

style="WIDTH: 44.33%; HEIGHT: 259px" src="http://pagead2.googlesyndication.com/cpa/ads?client=ca-pub-4577827332549849&cpa_choice=CAEaCB94-nvUZWENUB9QugJQtwRQTVAgULcCUB4&oe=gb2312&dt=1192720966468&lmt=1192720966&format=250x250_as&output=html&correlator=1192720966453&channel=2735220158&url=http%3A%2F%2Fyzkzoo.5d6d.com%2Fthread-67-1-1.html&color_bg=FFFFFF&color_text=000000&color_link=0000FF&color_url=008000&color_>實作下述三種算法，并用以下無序序列加以驗證：

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.key,L->r[i-1].key)){

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

      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;

    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];

  }

}

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);

}                   

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;

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

      L->r[j]=t;

    }

  }

}          

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;

    H->r=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.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.key);

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

  getch();

}

style="WIDTH: 52.39%; HEIGHT: 263px" src="http://pagead2.googlesyndication.com/cpa/ads?client=ca-pub-4577827332549849&cpa_choice=CAEaCKcC4yuPlq5lUDRQDVAtUK4BUENQCA&oe=gb2312&dt=1192819388296&lmt=1192819388&format=300x250_as&output=html&correlator=1192819388281&channel=2735220158&url=http%3A%2F%2Fyzkzoo.5d6d.com%2Fviewthread.php%3Ftid%3D70%26page%3D1%26extra%3Dpage%253D1&color_bg=FFFFFF&color_text=000000&color_link=0000FF&color_url=008000&color_>

style="WIDTH: 82.23%; HEIGHT: 74px" src="http://pagead2.googlesyndication.com/pagead/ads?client=ca-pub-4577827332549849&dt=1192818497343&lmt=1192818497&format=468x60_as&output=html&correlator=1192818497343&channel=1741427766&url=http%3A%2F%2Fyzkzoo.5d6d.com%2Fthread-68-1-1.html&color_bg=FFFFFF&color_text=000000&color_link=0000FF&color_url=008000&color_>

style="WIDTH: 58.41%; HEIGHT: 156px" src="http://pagead2.googlesyndication.com/pagead/ads?client=ca-pub-4577827332549849&dt=1192819750656&lmt=1192819750&prev_fmts=468x60_as%2C468x15_0ads_al_s%2C234x60_as&format=200x90_0ads_al_s&output=html&correlator=1192819750437&channel=1741427766&pv_ch=1741427766%2B&url=http%3A%2F%2Fyzkzoo.5d6d.com%2Fthread-68-1-1.html&color_bg=FFFFFF&color_text=000000&color_link=0000FF&color_url=008000&color_>