学步园

#include <stdio.h>
#include <malloc.h>
typedef int InfoType;

#define n 10					//假设的文件长度，即待排序的记录数目
typedef int KeyType;			//假设的关键字类型
typedef struct
 {	//记录类型
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据项，类型InfoType依赖于具体应用而定义
} RecType,SeqList;
// typedef RecType ;	//SeqList为顺序表类型，表中第0个单元一般用作哨兵


void InsertSort(SeqList *R)
{	//对顺序表R中的记录R[1..n]按递增序进行插入排序
	int i,j;
	for(i=2;i<=n;i++)				//依次插入R[2]，…，R[n]
		if(R[i].key<R[i-1].key)		//若R[i].key大于等于有序区中所有的keys，
		{							//则R[i]应在原有位置上
			R[0]=R[i];				//R[0]是哨兵，且是R[i]的副本
			j=i-1;
			do{		//从右向左在有序区R[1..i-1]中查找R[i]的插入位置
				R[j+1]=R[j];		//将关键字大于R[i].key的记录后移
				j--;
			}while(R[0].key<R[j].key);	//当R[i].key≥R[j].key时终止
			R[j+1]=R[0];				//R[i]插入到正确的位置上
		}
}
void SelectSort(SeqList *R)
{  //对顺序表R中的记录R[1..n]按递增序进行选择排序
	int i,j;
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
			if(R[i].key>R[j].key)
			{
				R[0]=R[i];
				R[i]=R[j];
				R[j]=R[0];
			}
}
void Bubblesort(SeqList *R)
{//冒泡排序
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n-i;j++)
			if(R[j].key>R[j+1].key)
			{
				R[0]=R[j];
				R[j]=R[j+1];
				R[j+1]=R[0];
			}
}
//---------归并排序(从小到大)---------------
void partion(SeqList *R,int low,int m,int high)
{
    int t,i;
     while(m<high)
     {
         t=m;  R[0]=R[t+1];
         while(R[t].key>R[0].key&&low<=t) t--;
         for( i=m;i>t;i--)
            R[i+1]=R[i];
         R[i+1]=R[0]; m++;
     }
}
void PartionSort(SeqList *R,int low,int high)
{//归并排序
	if(low>=high) return ;
	int m=(low+high)/2;
    PartionSort(R,low,m);
    PartionSort(R,m+1,high);
	     partion(R,low,m,high);
}

//-------------快速排序(从小到大排)--------------
int findMid(SeqList *R,int low,int high)
{
    int m=low;
    while(low<high)
    {
        while(R[m].key<=R[high].key&&m<high)high--;
        R[0]=R[m];R[m]=R[high];R[high]=R[0];
        m=high;
        while(R[low].key<=R[m].key&&low<m)low++;
        R[0]=R[m];R[m]=R[low];R[low]=R[0];
        m=low;
    }
    return m;
}
void Quicksort(SeqList *R,int low,int high)
{//快速排序
    if(low>=high) return ;

    int m=findMid(R,low,high);
    Quicksort(R,low,m);
    Quicksort(R,m+1,high);
}
int main()
{
	int i,low,high;
	SeqList *R;
	R=(SeqList *)malloc(15*sizeof(SeqList));
	printf("请输入欲排序的数：");
	for (i=1;i<=n;i++)
		scanf("%d",&R[i].key);
	printf("排序前：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	InsertSort(R);
	printf("直接插入排序：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
SelectSort(R);
printf("选择排序：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	Bubblesort(R);
printf("冒泡排序：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	Quicksort(R,1,10);
printf("快速排序：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
PartionSort(R,1,10);
printf("归并排序：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}