多种排序算法.cpp

关于数据结构的多种排序算法

#include<stdio.h>
#define N 8
#define TRUE 1
#define FALSE 0
#define LT(a,b) ((a)<(b))
#define MAXSIZE 20   /* 一个用作示例的小顺序表的最大长度 */
typedef int KeyType; /* 定义关键字类型为整型 */
typedef struct
 {
   KeyType key;   /* 关键字项 */
   int otherinfo; /* 其它数据项 */
 }RedType;        /* 记录类型 */

typedef struct
 {
   RedType r[MAXSIZE+1];  /* r[0]闲置或用作哨兵单元 */
   int length;            /* 顺序表长度 */
 }SqList;                 /* 顺序表类型 */

RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};

void print(SqList L)
 {
   int i;
   for(i=1;i<=L.length;i++)
     printf("(%d,%d)  ",L.r[i].key,L.r[i].otherinfo);
   printf("\n");
   printf("\n");
 }

/////////////////////////////////*直接插入排序*///////////////////////////////////////////////
void InsertSort(SqList *L)  /* 对顺序表L作直接插入排序 */
{ 
   int i,j;
   for(i=2;i<=(*L).length;++i)
     if LT((*L).r[i].key,(*L).r[i-1].key) /* "<",需将L.r[i]插入有序子表 */
     {
       (*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 cha_sort()
 {
   SqList l;
   int i;
   for(i=0;i<N;i++) /* 给l1.r赋值 */
     l.r[i+1]=d[i];
   l.length=N;
   printf("排序前:\n");
   print(l);
   InsertSort(&l);
   printf("直接插入排序后:\n");
   print(l);
 }
////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////*简单选择排序*/////////////////////////////////////////
 int SelectMinKey(SqList L,int i) /* 返回在L.r[i..L.length]中key最小的记录的序号 */
 { 
   KeyType min;
   int j,k;
   k=i;                 /* 设第i个为最小 */
   min=L.r[i].key;
   for(j=i+1;j<=L.length;j++)
     if(L.r[j].key<min) /* 找到更小的 */
     {
       k=j;
       min=L.r[j].key;
     }
   return k;
 }

 void SelectSort(SqList *L)   /* 对顺序表L作简单选择排序 */
 { 
   int i,j;
   RedType t;
   for(i=1;i<(*L).length;++i)  /*  选择第i小的记录，并交换到位 */
   { 
     j=SelectMinKey(*L,i);     /* 在L.r[i..L.length]中选择key最小的记录 */
     if(i!=j)                  /* 与第i个记录交换 */
     { 
       t=(*L).r[i];
       (*L).r[i]=(*L).r[j];
       (*L).r[j]=t;
     }
   }
 }

void xuan_sort()
 {
   SqList l;
   int i;
   for(i=0;i<N;i++)
     l.r[i+1]=d[i];
   l.length=N;
   SelectSort(&l);
   printf("简单选择排序后:\n");
   print(l);
 }
////////////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////*起泡排序的程序*//////////////////////////////////////////////
void bubble_sort(SqList *L) /* 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序) */
 {
   int i,j;
   RedType t;
   int change;
   for(i=N,change=TRUE;i>1&&change;--i)
   {
     change=FALSE;
     for(j=0;j<i;++j)
       if((*L).r[j].key>(*L).r[j+1].key)
       {
         t=(*L).r[j];
         (*L).r[j]=(*L).r[j+1];
         (*L).r[j+1]=t;
         change=TRUE;
       }
   }
 }

void mao_sort()
 {
   SqList l;
   int i;
   for(i=0;i<N;i++)
     l.r[i+1]=d[i];
   l.length=N;
   bubble_sort(&l);
   printf("起泡排序后:\n");
   print(l);
 }
//////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////*堆排序 */////////////////////////////////////////////////
typedef SqList HeapType; /* 堆采用顺序表存储表示 */
void HeapAdjust(HeapType *H,int s,int m) 
 { /* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数 */
   /* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */
   RedType rc;
   int j;
   rc=(*H).r[s];
   for(j=2*s;j<=m;j*=2)   /* 沿key较大的孩子结点向下筛选 */
   { 
     if(j<m&&LT((*H).r[j].key,(*H).r[j+1].key))
       ++j;               /* j为key较大的记录的下标 */
     if(!LT(rc.key,(*H).r[j].key))
       break;              /* rc应插入在位置s上 */
     (*H).r[s]=(*H).r[j];
     s=j;
   }
   (*H).r[s]=rc; /* 插入 */
 }

void HeapSort(HeapType *H) /* 对顺序表H进行堆排序 */
 { 
   RedType t;
   int i;
   for(i=(*H).length/2;i>0;--i) /* 把H.r[1..H.length]建成大顶堆 */
     HeapAdjust(H,i,(*H).length);
   for(i=(*H).length;i>1;--i)
   { /* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */
     t=(*H).r[1];
     (*H).r[1]=(*H).r[i];
     (*H).r[i]=t;
     HeapAdjust(H,1,i-1); /* 将H.r[1..i-1]重新调整为大顶堆 */
   }
 }

void dui_sort()
 {
   HeapType h;
   int i;
   for(i=0;i<N;i++)
     h.r[i+1]=d[i];
   h.length=N;
   HeapSort(&h);
   printf("堆排序后:\n");
   print(h);
 }
/////////////////////////////////////////////////////////////////////////////////////////////



///////////////////////////////*快速排序的函数*//////////////////////////////////////////////
int Partition(SqList *L,int low,int high)
 { /* 交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其 */
   /* 所在位置，此时在它之前（后）的记录均不大（小）于它。算法10.6(b) */
   KeyType 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)/* 对顺序表L中的子序列L.r[low..high]作快速排序*/
 { 
   int pivotloc;
   if(low<high)     /* 长度大于1 */
   { 
     pivotloc=Partition(L,low,high); /* 将L.r[low..high]一分为二 */
     QSort(L,low,pivotloc-1);        /* 对低子表递归排序，pivotloc是枢轴位置 */
     QSort(L,pivotloc+1,high);       /* 对高子表递归排序 */
   }
 }

 void QuickSort(SqList *L)   /* 对顺序表L作快速排序 */
 { 
   QSort(L,1,(*L).length);
 }

void kuai_sort()
 {
   SqList l;
   int i;
   for(i=0;i<N;i++)
     l.r[i+1]=d[i];
   l.length=N;
   QuickSort(&l);
   printf("快速排序后:\n");
   print(l);
 }
////////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////* 希尔排序 *//////////////////////////////////////////////
void ShellInsert(SqList *L,int dk)
 { /* 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比， */
   /* 作了以下修改： */
   /* 1.前后记录位置的增量是dk,而不是1; */
   /* 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。算法10.4 */
   int i,j;
   for(i=dk+1;i<=(*L).length;++i)
     if LT((*L).r[i].key,(*L).r[i-dk].key)/* 需将(*L).r[i]插入有序增量子表 */
     { 
       (*L).r[0]=(*L).r[i]; /* 暂存在(*L).r[0] */
       for(j=i-dk;j>0&&LT((*L).r[0].key,(*L).r[j].key);j-=dk)
         (*L).r[j+dk]=(*L).r[j]; /* 记录后移，查找插入位置 */
       (*L).r[j+dk]=(*L).r[0]; /* 插入 */
     }
 }

 void print3(SqList L)
 {
   int i;
   for(i=1;i<=L.length;i++)
     printf("%d ",L.r[i].key);
   printf("\n");
 }

 void ShellSort(SqList *L,int dlta[],int t)/* 按增量序列dlta[0..t-1]对顺序表L作希尔排序 */
 { 
   int k;
   for(k=0;k<t;++k)
   {
     ShellInsert(L,dlta[k]); /* 一趟增量为dlta[k]的插入排序 */
     printf("第%d趟排序结果: ",k+1);
     print3(*L);
   }
 }

#define T 3
void xi_sort()
{ 
   printf("希尔排序 \n");
   SqList l;
   int i,dt[T]={4,3,1}; /* 增量序列数组 */
   for(i=0;i<10;i++)
     l.r[i+1]=d[i];
   l.length=N;
   ShellSort(&l,dt,T);
   printf("希尔排序后: \n");
   print(l);
 }
//////////////////////////////////////////////////////////////////////////////////////////////


void main()
{
	cha_sort();       //直接插入排序
    xuan_sort();      //简单选择排序
    mao_sort();       //起泡排序
    dui_sort();       //堆排序
    kuai_sort();      //快速排序
    xi_sort();        //希尔排序
}