第三题.cpp

数据结构之中排序程序的实现

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAXSIZE 20
#define N 6
#define M 6

typedef struct{
	int r[MAXSIZE+1];
	int length;
}SqList;

void InsertSort(SqList &L){//直接插入排序
	int i,j,n;
	printf("请输入你要进行排序的数字个数：");
	scanf("%ld",&n);
	printf("请输入你要进行排序的数字：");
    for(i=1;i<=n;i++){    scanf("%ld",&L.r[i]);   }
	for(i=2;i<=n;i++)
	{    if(L.r[i]<L.r[i-1]){
		    L.r[0]=L.r[i];
			for(j=i-1;L.r[0]<L.r[j];j--)
			L.r[j+1]=L.r[j];
			L.r[j+1]=L.r[0];
	}
	}
    for(i=1;i<=n;i++)
	printf("%ld ",L.r[i]);
}//InsertSort

void BInsertSort(SqList &L){//折半插入排序
    int i,j,n,m,low,high;
	printf("请输入你要进行排序的数字个数：");
	scanf("%ld",&n);
	printf("请输入你要进行排序的数字：");
    for(i=1;i<=n;i++){    scanf("%ld",&L.r[i]);   }
	for(i=2;i<=n;i++){
		L.r[0]=L.r[i];
		low=1;high=i-1;
		while(low<=high){
			m=(low+high)/2;
			if(L.r[0]<L.r[m]) high=m-1;
			else low=m+1;
		}//while
		for(j=i-1;j>=high+1;j--)L.r[j+1]=L.r[j];
		L.r[high+1]=L.r[0];
	}//for
    for(i=1;i<=n;i++)
	     printf("%ld ",L.r[i]);
}//BInsertSort

void SelectSort(){//简单选择排序
   int i,j,n,max,Num;
   int Nums[10];
   printf("请输入你要进行排序的数字个数:");
   scanf("%ld",&n);
   printf("\n请输入你要进行排序的数字:");
   for (i=1;i<=n;i++)
   {      
       scanf("%ld",&Nums[i]);
   }
   for (i=1;i<=n;i++)
   {   max=0;
       for (j=0;j<=n-i;j++)
	   {
           if (Nums[max]<Nums[j])
		   {
              max=j;
		   }
	   }
       if (Nums[max]!=Nums[n-i])
	   {
          Num=Nums[max];
          Nums[max]=Nums[n-i];
          Nums[n-i]=Num;
	   }
   }
   for (i=1;i<=n;i++)
   {
      printf("%d ",Nums[i]);
   }  
}//SelectSort

void build(int *a,int i,int n){// 建堆函数
    int k,j,tmp;
    k=i;
    j=2*k+1;
    while(j<=n){
        if(j<n && a[j]<a[j+1])
            j++;
        if(a[k]>=a[j])break;
        tmp=a[k];
        a[k]=a[j];
        a[j]=tmp;        
        k=j;
        j=2*j+1;
    }
}

void prnt(int *a,int n){// 打印数组函数
    int i;
    printf("\n");
    for(i=0;i<n;i++){
        printf("%3d",a[i]);
    }
    printf("\n");
}

void prnthp(int *a,int b1,int b2){// 打印堆函数
    int i,j,cnt,start,tmp,h=0,sum=0,item=1,size;
    size=b2-b1+1;
    while(sum<=size){
        sum+=item;
        h++;
        item*=2;
    }
    item=1;
    cnt=0;
    start=b1;
    tmp=1;  
    printf("  堆：\n");
    while(1){
        for(i=0;i<h;i++){
                for(j=0;j<h-i;j++)
                                printf("    ");
                 for(j=0;j<i+1;j++)printf(" "); 
                for(j=0;j<tmp;j++){
                                if(cnt>size-1)goto end;
                                printf("%4d",a[cnt++]);
                }
                printf("\n");
                tmp*=2;
        }       
     }
     end:
          printf("\n");         
          return;                  
}

void prntar(int *a,int b2,int len){// 打印已排序数组函数
  int i; 
  printf("  已排序：\n");
  for(i=0;i<b2;i++){
    printf("   ");
  }          
  for(i=b2;i<=len;i++){
    printf("%3d",a[i]);
  }          
  printf("\n");
} 
void HeapSort(){
    int a[50],i,tmp,sum,len;
    printf("              堆排序\n");
    printf("\n***************************************\n");    
    printf("\n  请输入要排序的数字个数：\n");
    scanf("%3d",&len);    
    printf("\n  请输入要排序的数字：\n");
    for(i=0;i<len;i++)
        scanf("%3d",&a[i]);        
    tmp=1;sum=0;
    while(sum+tmp<=len){
        sum+=tmp;    
        tmp*=2;
    }
    printf("\n****************************************\n");    
    printf("\n  初始数组：            \n");    
    prnt(a,len);        
    for(i=sum-1;i>=0;i--)
        build(a,i,len-1);       
    prnthp(a,0,len-1);          
    for(i=0;i<len-1;i++){
        tmp=a[0];
        a[0]=a[len-1-i];
        a[len-1-i]=tmp;
        build(a,0,len-2-i);
        prnthp(a,0,len-2-i);
        prntar(a,len-1-i,len-1);        
    }
    printf("\n*******************************************\n");
    printf("\n  排序结果：\n");        
    prnt(a,len);
    printf("\n*******************************************\n\n");    
}//HeapSort

void QuickSort(int a[],int p,int q) 
{     int i=p,j=q,temp=a[p]; 
      do 
	  {     while(a[q]>=temp && p<q)q--; //右端扫描 
            if (p<q) 
			{a[p]=a[q];p++;} 

            while(a[p]<=temp && p<q)p++;//左端扫描
            if (p<q) 
			{a[q]=a[p];q--;} 
	  }while(p<q); 
      a[p]=temp; 
      if (i<p) QuickSort(a,i,p-1);//对左端子集进行扫描
      if (q<j) QuickSort(a,q+1,j);//对右端子集进行扫描
}//QuickSort

void main()
{   int i,length,a[M];
    SqList L;
    do
	{  printf("\n\n\n\n\n");
       printf("                     1.直接插入排序                    \n");
	   printf("                     2.折半插入排序                    \n");
	   printf("                     3.简单选择排序                    \n");
	   printf("                     4.堆排序                          \n");
	   printf("                     5.快速排序                        \n");
	   printf("                     6.退出                            \n");
	   printf("*******************************************************\n");
       printf("                   选择你要进行排序的方法              \n");
	   scanf("%ld",&i);
	   while(i<1||i>6)
	   {     printf("输入有误，请重新输入(0<i<7)：");
	         scanf("%ld",&i);
	   }//while
	   switch(i)
	   {
	       case 1: InsertSort(L);break;
	       case 2: BInsertSort(L);break;
		   case 3: SelectSort();break;
		   case 4: HeapSort();break;
		   case 5: printf("请输入你要进行排序的数字个数:"); 
                   scanf("%d",&length); 
                   printf("请输入你要进行排序的数字:"); 
                   for(i=0;i<length;i++) 
                       scanf("%d",&a[i]); 
                   QuickSort(a,0,length-1); 
                   for(i=0;i<length;i++) 
                       printf("%d ",a[i]);
				   break;
		   case 6: return;
	   }
	   }while(i);
}