排序算法比较 new.cpp

直接插入排序

/*********************************************************************************************

                        *******************************
                        *姓名： 杨刚            *
                        *学号： 040640316     *
                        *最终完成时间： 2007年1月8日" *
                        *******************************
/********************************************************************************************/


#include<stdio.h>
#include<stdlib.h>
#include<time.h>//此头文件用于统计排序的所用时间
#include"math.h"//此头文件用于产生随机函数
typedef long clock_t;
#define MAXSIZE 30000
typedef int KeyType;


//定义关键字的结构
typedef struct
{
	KeyType key;
}RedType;


//定义线性表的结构
typedef struct
{
	RedType r[MAXSIZE+1];
	int length;
}SqList;


//用于打印的函数
void PrintSq(SqList L)
{
	int i;
	printf("输出比较结果为：\n");
	for(i=1;i<=L.length;i++)
	{
		printf("%8d",L.r[i].key);
		if(i%10==0)
        printf("\n");
	}
	

}


//用于比较的函数
int LT(SqList L,int i,int j)
{
        if(L.r[i].key<L.r[j].key)
			return 1;
		else 
			return 0;
}


//用于交换的函数
void Change(SqList &L,int i,int j)
{	int temp;	
	temp=L.r[i].key;
	L.r[i].key=L.r[j].key;
	L.r[j].key=temp;
}



//1.插入排序
void InsertSort(SqList &L)
{
	for(int i=2;i<=L.length;++i)
		if(LT(L,i,i-1))
		{                
			L.r[0]=L.r[i]; //复制为哨兵
			L.r[i]=L.r[i-1];
			for(int j = i-2;LT(L,0,j); --j)
			{
		       L.r[j+1]= L.r[j];//记录后移
			}	
			L.r[j+1]=L.r[0];//插入
		}
		PrintSq( L);
}//InsertSort



//2.折半插入排序
void BInsertSort(SqList &L)
{
	int low,high,mid;
	for(int i=2;i<=L.length ;++i)
	{
	  L.r[0]=L.r[i]; //将L.r[i]暂存在L.r[0]
	  low = 1; 
	  high = i-1;

	  while(low<=high)
	  { 
		//在r[low..high]中折半查找有序插入的位置
		mid = (low+high)/2;
		if(LT(L,0,mid))
			high = mid - 1;//插入在低半区
		else
			low = mid + 1;//插入在高半区
	  }//while

	 for(int j=i-1;j>=high+1;--j)     
		L.r[j+1]= L.r[j];//记录后移

	  L.r[high+1]=L.r[0]; //插入

	}//for
	PrintSq( L);
}//BInsertSort





//3.起泡排序
void BubbleSort(SqList &L)
{
	int i,j;
	for(j=1;j<=L.length-1;j++)
	{
		for(i=1;i<=L.length-j;i++)
			if(LT(L,i+1,i))
			{
				Change(L,i+1,i);
			}
	}
	PrintSq( L);
}//BubbleSort



//4.快速排序
int Partition(SqList &L,int low,int high)
{
	//交换顺序表l中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置
	//此时在它之前（后）的记录均不大（小）于它
	
	L.r[0] = L.r[low];
	int 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[high].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]作快速排序

	if(low<high)
	{
		int pivotkey = Partition(L, low, high);
        Qsort(L, low,pivotkey-1);
		Qsort(L,pivotkey+1,high);
	}
	//PrintSq( L);
}//Qsort



//5.简单选择排序 
int SelectMinKey(SqList &L , int k)
{
	//对顺序表l作选择排序

	int i;
	for(i=k;i<=L.length;i++)
	{		
	    if(LT(L,i,k))
			k=i;
	}
	return k;
			  
}//SelectMinKey

void SelectSort(SqList &L)
{
	int j;
	for(int i=1;i<L.length;++i)          //选择第i小的记录，并交换到位 
	{
		j=SelectMinKey(L,i);             //在r[i..L.length]中选择Key最小的记录
		if(i!=j)
			Change(L,i,j);               //与第i个记录交换
	}
	PrintSq( L);
}//SelectSort



//6.堆排序
typedef SqList HeapType;

void HeapAdjust(HeapType &L,int s,int m)
{   
	//Shift(L,0,s);
    RedType rc=L.r[s];
	for(int j=2*s;j<=m;j*=2)
	{
		if(j<m&&LT(L,j,j+1))//沿key较大的孩子结点向下筛选
			++j; //j为key较大的记录的下标
		if(!LT(L,0,j))
		    break; //rc应插在位置s上
		s=j;
	}

	L.r[s]=rc;//插入  
}//HeapAdjust

void HeapSort(HeapType &L)
{
	//对顺序表l进行排序
	for(int i = L.length/2;i>0;--i)
		HeapAdjust(L,i,L.length);
	for(i = L.length ; i>1;--i)
	{
		Change(L,1,i);
	    HeapAdjust(L,1,i-1);
	}
	PrintSq( L);
}//HeapSort



//7.基数排序

//定义新的数据类型
#define MAX_NUM_OF_KEY 4        //关键字项数的最大值
#define MAX_SPACE 10000 
        
typedef struct
{
	int keys[MAX_NUM_OF_KEY];   //关键字
	int next;
}SLCell;//静态链表的结点类型
                        	
typedef struct
{
	SLCell r[MAX_SPACE];        //静态链表的可利用空间，r[0]为头结点　
	int keynum;                 //记录的当前关键字个数
	int recnum;                 //静态链表的长度 
}SLList;                        //静态链表的类型

typedef int ArrType[10];        //指针数组类型

//change函数
void change(int a,int keys[4])
{
    //本函数用于将int to int[4]
	keys[0]=a/1000;a-=keys[0]*1000;
	keys[1]=a/100; a-=keys[1]*100;
	keys[2]=a/10;  a-=keys[2]*10;
    keys[3]=a;
}

int Change(int &a,int keys[4])
{
	a=0;
	a+=keys[0]*1000;
	a+=keys[1]*100;
	a+=keys[2]*10;
	a+=keys[3];
	return a;
}

//SWAP函数
//用于将L.r[i]与L.r[j]交换，借助中间变量L.r[0]
void SWAP(int i,int j,SLList &L){
	SLCell temp;
	int shiftcount;
	shiftcount+=3;            //移动次数加3
	temp=L.r[j];
    L.r[j]=L.r[i];
    L.r[i]=temp;
}//SWAP

void Arrange(SLList &SL) 
{  
  // 根据静态链表SL中各结点的指针值调整记录位置，
  // 使得SL中记录按关键字非递减有序顺序排列

  int i;
  int p,q;
  p = SL.r[0].next;  // p指示第一个记录的当前位置
  for (i=1; i<SL.recnum; ++i) { 
    // SL.r[1..i-1]中记录已按关键字有序排列，
    // 第i个记录在SL中的当前位置应不小于i
    while (p<i)  // 找到第i个记录，并用p指示其在SL中当前位置
      p = SL.r[p].next;
    q = SL.r[p].next; // q指示尚未调整的表尾
    if (p!= i) {
      SWAP(i,p,SL);
      SL.r[i].next=p; // 指向被移走的记录，使得以后可由while循环找回
    }
    p=q;              // p指示尚未调整的表尾，为找第i+1个记录作准备
  }
} // Arrange

void Distribute(SLList &L, int i, ArrType &f, ArrType &e) {  
  // 静态链表L的r域中记录已按(keys[0],...,keys[i-1])有序，
  // 本算法按第i个关键字keys[i]建立RADIX个子表，
  // 使同一子表中记录的keys[i]相同。f[0..RADIX-1]和e[0..RADIX-1]
  // 分别指向各子表中第一个和最后一个记录
  int j, p;
  for (j=0; j<10; ++j)
  {// 各子表初始化为空表
	  f[j] = 0;e[j]=0;
  }
  
  for (p=L.r[0].next;  p;  p=L.r[p].next)
  {
    j = L.r[p].keys[i];             // 将记录中第i个关键字映射到[0..RADIX-1]
    if (!f[j])
	{ 	f[j] = p;
		e[j] = p; 
	}		
    else
	{  L.r[e[j]].next=p;	
	   e[j]=p;                     // 将p所指的结点插入第j个子表中
	}
  }
} // Distribute

void Collect(SLList &L, int i, ArrType f, ArrType e) 
{ 
  // 本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成
  // 一个链表，e[0..RADIX-1]为各子表的尾指针
  int j,t;
  for (j=0; !f[j]; j++);  // 找第一个非空子表，succ为求后继函数: ++
  L.r[0].next = f[j];     // L.r[0].next指向第一个非空子表中第一个结点
  t = e[j];
  while (j<10){
    for (j=j+1; j<10 && !f[j]; j++);       // 找下一个非空子表
    if (j<10)             // 链接两个非空子表
      { L.r[t].next = f[j];  t = e[j]; }
  }
  L.r[t].next = 0;        // t指向最后一个非空子表中的最后一个结点
 // printSL(L);
} // Collect

void RadixSort(SLList &L)
 {  
   // L是采用静态链表表示的顺序表。
   // 对L作基数排序，使得L成为按关键字自小到大的有序静态链表，
   // L.r[0]为头结点。
   int i;
   
   ArrType f, e;
   for (i=1; i<L.recnum; ++i) L.r[i-1].next = i;
   L.r[L.recnum-1].next = 0;       // 将L改造为静态链表
   for (i=3; i>=0; i--)
   {  
      // 按最低位优先依次对各关键字进行分配和收集
      Distribute(L, i, f, e);    // 第i趟分配
      Collect(L, i, f, e);       // 第i趟收集
     
   }
   Arrange(L);                   //调整L中记录，使按关键字非递减有序顺序排列
  
} // RadixSort


//printSL函数

//用于打印排序后的静态表
void printsSL(SLList L)      
{   
	int i,k;
	
	for(i=1; i<L.recnum; i++)
	{
		Change(k,L.r[i].keys);
		printf("%8d",k);
	}
}


int choose()
{
	int i;
	printf("**********************************************************\n");
	printf("---------------请从1到8号编号中选择你要的操作-------------\n");
	printf("**********************************************************\n");
	printf("1：直接插入排序 2: 折半插入排序3:起泡排序 4:快速排序      \n");
	printf("5: 简单选择排序 6: 堆排序      7:基数排序 8:退出          \n");
    printf("******************************************************\n");
	printf("请输入你要的操作：");
	scanf("%d",&i);
	return i;

}
//***************************************程序的主函数******************************************
void main()
{
	SqList L;
	SLList l;//此处定义基数排序的线形表结构 
    clock_t t1,t2;
	int UseTime;//用于统计排序所用时间
	
	printf("---------------------请输入您所要排序的元素个数-------------\n");
	int num;
	scanf("%d",&num);
	while(num<500&&num>30000&&num/500!=0)
	{
		printf("你的输入有误,请重输!\n");
		scanf("%d",&num);
	}
    L.length=num;l.keynum=4;l.recnum=num+1;
	srand(time(0));
	int low,high;
	int i;
    srand(time(0)); 
    for(int j=1;j<=num;j++)
    {
    i=rand()%10000;
    printf("%8d",i);
	L.r[j].key=i;
	change(i,l.r[j].keys);
    }
	printf("\n");
	int t=choose();//主菜单的显示
	while(t)
	{
		switch(t)
		{
        case 1 :t1=clock();
				InsertSort(L);//插入排序
			    t2=clock();
				printf("\n");
				printf("直接插入排序所用时间为:");
                UseTime=t2-t1;
				printf("%d毫秒",UseTime);//显示排序所用时间
				printf("\n\n\n\n\n");
				t=choose();
				break;
		case 2 :
		     	t1=clock();
			    BInsertSort(L);//折半排序
				printf("\n");
				printf("折半插入排序所用时间为:");
				t2=clock();
			    UseTime=t2-t1;
				printf("%d毫秒",UseTime);//显示排序所用时间
				printf("\n\n\n\n\n");
				t=choose();
				break;
	    case 3 :
			    t1=clock();
				BubbleSort(L);//冒泡排序
				t2=clock();
				printf("\n");
				printf("起跑排序所用时间为:");
				UseTime=t2-t1;
				printf("%d毫秒",UseTime);//显示排序所用时间
			    printf("\n\n\n\n\n");
				t=choose();
				break;
		case 4 :SqList L1=L;
			    t1=clock();
			    low=1;
			    high=num;
				Qsort(L1, low, high);//快速排序
				t2=clock();
				PrintSq(L1);
				printf("\n");
                printf("快速排序所用时间为:");	 
                UseTime=t2-t1;
				printf("%d毫秒",UseTime);//显示排序所用时间
				printf("\n\n\n\n\n");
				t=choose();
				break;
		case 5 :
			    t1=clock();
			    SelectSort(L);//选择排序
				t2=clock();
				printf("\n");
				printf("简单选择排序所用时间为: ");
				UseTime=t2-t1;
				printf("%d毫秒",UseTime);//显示排序所用时间
			    printf("\n\n\n\n\n");
				t=choose();
				break;
		case 6 :t1=clock();
			    HeapSort(L);//堆排序
				t2=clock();
				printf("\n");
				printf("堆排序所用时间为: ");
				UseTime=t2-t1;
                printf("%d毫秒",UseTime);//显示排序所用时间
		        printf("\n\n\n\n\n");
				t=choose();
				break;
	    case 7 :t1=clock();
			    RadixSort(l);//基数排序
				printsSL(l);
				t2=clock();
				printf("\n");
				printf("基数排序所用时间为: ");
				UseTime=t2-t1;
				printf("%d毫秒",UseTime);//显示排序所用时间
				printf("\n\n\n\n\n");
				t=choose();
				break;
		case 8 :printf("            ******************************************\n");
                printf("                                                      \n");
                printf("                      THANK YOU FOR YOUR FAVOR  !!!           \n");
                printf("                                                      \n");
                printf("            ******************************************\n");
			exit(0);
				
		default: 
			{
				printf("您输入的数值超出了范围，请重输！\n\n\n\n");
				t=choose();
				break;
			}
		}
	}

}