arragement.cpp

数据结构涉及到的所有排序算法

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<iostream.h>
#define MAXSIZE 20
#define N  20
#define LT(a,b) ((a)<(b)) //宏定义
typedef int keyType; //定义关键字KeyType为int
typedef int InfoType;   //定义关键字InfoType为int
typedef struct{//RedType结构定义
	keyType key;
	//InfoType  otherinfo;//记录中其他信息域类型
}RedType;

typedef struct{//SqList结构定义
	RedType r[MAXSIZE+1];//定义大小
	int length;//length为待排记录的个数
}SqList;


//直接插入排序
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[0]=L->r[i];//将待插入的记录放在哨兵r[0]中
       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,mid;
  for(i=2;i<=L->length;++i)
  {
	  L->r[0]=L->r[i];//保存待插入的记录
  low=1;high=i-1;//查找的上下界
  while(low<=high){
	  mid=(low+high)/2;//确定插入位置
	  if(LT(L->r[0].key,L->r[mid].key))
		  high=mid-1;//到左半边查找
	  else low=mid+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)
// 对数组L中由r[low]直至r[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];//将小于基准的记录复制到r[low]
	  while(low<high&&L->r[low].key<=pivotkey)
		  ++low;//从左向右找到大于基准的记录
      L->r[high]=L->r[low]; //将小于基准的记录复制到r[high]
  }
  L->r[low]=L->r[0];//将基准记录复制到合适位置
  return low;//并返回基准记录位置
}

//函数
void QSort(SqList *L,int low,int high)////对数组L中r[low]至r[high]的记录进行快速排序
{
	int pivotloc; //一趟划分后基准记录位置
	if(low<high){
		pivotloc=Partition(L,low,high);//对记录r[low]至r[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)//对数组L中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)//对数组L进行简单选择排序
{RedType t;
 int i,j;
 for(i=1;i<L->length;++i)
 {j=SelectMinKey(*L,i);
  if(i!=j)//若最小的记录不是r[i]，则与r[i]交换
  {   t=L->r[i];
      L->r[i]=L->r[j];
      L->r[j]=t;
    }
  }
}





//堆排序
typedef SqList HeapType;
void HeapAdjust(HeapType *H,int s,int m)
// r[s]...r[m]是以r[s]为根的完全二叉树，该函数将整个序列r[s....m]调整为大顶堆
{  int j;
RedType rc;//附加的空单元
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)//对数组H的记录进行堆排序
{ int i;
  RedType t;//调用一次筛选函数，将数组H中记录建为大顶堆
  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);   //将剩余记录调整为堆
  }
}


//起泡排序
void BubbleSort(SqList *L)
{ int i,j;
  RedType t;
  for(i=1;i<L->length;i++)
  {for(j=L->length-1;j>=i;j--)
   if(L->r[j+1].key<L->r[j].key)
   {t=L->r[j+1];
    L->r[j+1]=L->r[j];
	L->r[j]=t;
   }
  }
}

//希尔排序
void ShellSort(SqList *L)
{ int i,j,dk,n;
  n=L->length;
  dk=n/2;
  while(dk>0)
  {
  for(i=dk+1;i<=L->length;++i)
	  if(LT(L->r[i].key,L->r[i-dk].key)){
		  L->r[0]=L->r[i];
		  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];
	  }
	  dk=dk/2;
}
}
/*------------------------------------------------------------------*/
//----------------------------归并排序流程---------------------------
//归并排序
void Merge(SqList *L, int low,int m,int high)
//将两个有序表R[low..m]he R[m+1..high]归并为一个有序表R[low,high]
{int i=low,j=m+1,k=0;//k是temp的下标，i,j分别为第1，2段的下标 
 RedType *temp;
 temp=(RedType*)malloc((high-low+1)*sizeof(RedType));//用于临时保存有序序列 
 while(i<=m&&j<=high)//在第1段和第2段均未扫描完时循环 
 {if(LT(L->r[j].key,L->r[i].key))//将第1段中的记录放入temp中 
 {temp[k++]=L->r[j];
 j++;}
  else //将第2段中的记录放入temp中 
  {temp[k++]=L->r[i];
   i++;
  }
 }
 while(i<=m)//如果第一段还有元素存在，则将其复制到temp中
 temp[k++]=L->r[i++];
 while(j<=high)//如果第二段还有元素存在，则将其复制到temp中
 temp[k++]=L->r[j++];
 for(k=0,i=low;i<=high;i++,k++)//将temp复制回L中 
	 L->r[i]=temp[k];
}


//二路归并排序
void MSort(SqList *L,int low,int high)
{ int m;
  if(low<high)
  {m=(low+high)/2;
   MSort(L,low,m);
   MSort(L,m+1,high);
   Merge(L,low,m,high);
  }
}

void MergeSort(SqList *L)
{MSort(L,1,L->length);
}
 
//------------------------------------------------------
//-----------------归并排序结束-------------------------

typedef struct node{
	RedType r;
	struct node *next;
}RecType;

void RadixSort(SqList *L)//基数排序
{int i,j,k,d;
RecType *p,*s,*t,*head[10],*tail[10];//定义各链队的首尾指针 
//---------------------------------------------------
//将数组中的元素转化为链表,从而利用基数排序
//---------------------------------------------------
for(i=1;i<=L->length;i++)
{s=(RecType*)malloc(sizeof(RecType));
 s->r.key=L->r[i].key;
 //s->r.otherinfo=L->r[i].otherinfo;
 if(i==1){
	 t=s;
	 p=s;//使p保持指向链表的头结点,为后续做好准备

 }
 else{t->next=s;
   t=s;
 
 }
 t->next=NULL;
}
//----------------建立链表结束---------------------
//-------------------------------------------------
d=1;
for(i=1;i<8;i++)//最多能处理这么多数
{
	for(j=0;j<10;j++)
	{head[j]=tail[j]=NULL;//初始化各链队首、尾指针
	}
//---------将各位元素处理到对应的链表中-----------
//------------------------------------------------
while(p!=NULL)//对于原链表中的每个结点循环 
{k=p->r.key/d;//得到对应的每一位元素
k=k%10;
if(head[k]==NULL)//进行分配 ,建立头指针
{head[k]=p;
 tail[k]=p;
}
else{tail[k]->next=p;
 tail[k]=p;
}
p=p->next;//取下一个待排序的元素 

}
p=NULL;//对后续链表作准备
//---------------------------------------------------
//对每一个链队循环
for(j=0;j<10;j++) 
{if(head[j]){
	if(p==NULL){
		p=head[j];
		t=tail[j];
	}
	else{
		t->next=head[j];
		t=tail[j];
	}
}
}
t->next=NULL;//最后一个结点的next置为空 
d=d*10;
}
i=1;
while(p){
	L->r[i]=p->r;
	i++;
	p=p->next;
}
}


//基数排序二

 /* typedef struct node{
	RedType r;
	struct node *next;
  }RecType;
//将数组元素转化为链表形式
RecType *createLink(SqList *L)
  {RecType *p,*s,*t;
    int i;
	for(i=1;i<=L->length;i++)
	{s=(RecType*)malloc(sizeof(RecType));
     s->r.key=L->r[i].key;
    // s->r.otherinfo=L->r[i].otherinfo;
     if(i==1)
	 p=t=s;
     else
	 {t->next=s;
     t=s;
	 }
   
	}
    t->next=NULL;
	return p;
}

void Distrubute(RecType *p,SqList *L,int d)
  {RecType *head[10],*tail[10];//建立十个链表作为分配
   RecType *t,*s;
   int j,k,m=1,count[10];
   for(j=0;j<10;j++)
   {head[j]=tail[j]=NULL;//链表的初始化
   count[j]=1;
   }
   while(p)
   {k=p->r.key/d;
    k=k%10;
	if(count[k]==1)
		head[k]=tail[k]=p;
	else
	{tail[k]->next=p;
	 tail[k]=p;
	}
	count[k]++;
	p=p->next;
   }

   for(j=0;j<10;j++)//将链表串联起来
	   if(head[j])
	   {
		   if(m==1)
		   {p=t=head[j];
		    s=tail[j];
		   }
		   else
		   {s->next=head[j];
		    s=tail[j];
		   }
	   }
      s->next=NULL;
	  int i=1;
	  while(t)
	  {L->r[i]=t->r;
	   i++;
	   t=t->next;
	  }
	  cout<<"整理结果:"<<endl;
  for(i=0;i<L->length;++i)
	 { cout<<L->r[i].key<<"  ";
      if(i%10==0) cout<<endl;
  }
  cout<<endl;
	  
  }

  void RadixSort(SqList *L)//基数排序
  {   RecType * p;
      p=createLink(L);
	  int i,d=1;
	  for(i=0;i<6;i++)
      {Distrubute(p,L,d);
	   d=d*10;
	  }
  }*/

   

   





 void main()
{
  //可视化的界面操作
	 printf("---------------------------------------\n");
	 printf("---------排序选择菜单------------------\n");
	 printf("---------------------------------------\n");
	 printf(" 1------直接插入排序-------------------\n");
	 printf(" 2------折半插入排序-------------------\n");
	 printf(" 3------快速排序-----------------------\n");
	 printf(" 4------选择排序-----------------------\n");
	 printf(" 5------堆排序-------------------------\n");
	 printf(" 6------起泡排序-----------------------\n");
	 printf(" 7------希尔排序-----------------------\n");
	 printf(" 8------归并排序-----------------------\n");
	 printf(" 9------基数排序-----------------------\n");

  printf("以下个数为随机产生的数，用以检验各种排序方法:\n");
  SqList s;
  int i,k;
  for(i=1;i<=N;i++)
   {
      s.r[i].key=rand();
      printf("%d  ",s.r[i].key);
	  if(i%10==0) printf("\n");

    }

   s.length=i-1;


  printf("请按上诉菜单选择1-7数字键来选择相应的排序函数\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;
	case 6:
      BubbleSort(&s);   //起泡排序
	  break;
	case 7:
      ShellSort(&s);    //希尔排序
	  break;
	case 8:
      MergeSort(&s);    //归并排序
	  break;
	case 9:
      RadixSort(&s);   //基数排序
	  break;
	default:
		printf("没有该函数可选择！\n");
  }
 printf("\n已排序好的记录值：\n");
 for(i=1;i<N;i++)
	  
  {printf("%d  ",s.r[i].key);
  if(i%10==0)  printf("\n");}
  printf("\n\n\t请按任意键退出！\n");
  getchar();
}