sort.txt

对顺序表用Ｃ语言实现直接插入排序、折半插入排序、希尔排序、快速排序、选择排序、冒泡优化排序、堆排序

对顺序表用Ｃ语言实现直接插入排序、折半插入排序、希尔排序、快速排序、选择排序、冒泡优化排序、堆排序，代码如下： 
 

#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include <conio.h>
#define MAXSIZE 100
typedef int RedType;
typedef struct SqList
{
       RedType INT[MAXSIZE+1];
       int length;      
}SqList; 
SqList L;
void TIME()                                      //获得系统时间
{
 static char *week[]={"一","二","三","四","五","六","日"};
 time_t t;
 struct tm *tp;
 t=time(NULL);
 tp=localtime(&t);
 printf("\t　       ─────────────────────\n");
 printf("\t\t    现在是:%d年%d月%d日",tp->tm_year+1900,tp->tm_mon+1,tp->tm_mday);   
 printf(" %d:%d:%d ",tp->tm_hour,tp->tm_min,tp->tm_sec,tp->tm_wday); 
 printf("星期%s\n",week[(tp->tm_wday)-1]);
}
void PRINT(SqList *L)                             //打印排序结果
{
 int i;
 printf("\t\t");
 for(i=1;i<=L->length;i++)
     printf("%d ",L->INT[i]);
 printf("\n");
}
void STINSORT(SqList *L)                         //直接插入排序
{
 int i,j;
 for(i=2;i<=L->length;i++)                    //依次插入INT[2]，…，INT[n]
 {
  L->INT[0]=L->INT[i];                     //以INT[0]为哨兵
  j=i-1;
  while(L->INT[j]>L->INT[0])
  {
   L->INT[j+1]=L->INT[j];
   j--;
  }
  L->INT[j+1]=L->INT[0];
 }
}
void BIS_INT(SqList *L)                          //折半插入排序
{  
 int i,j,low,high,mid;
 for(i=2;i<=L->length;++i)
       if(L->INT[i]<L->INT[i-1])
    {
     L->INT[0] = L->INT[i];
     high=i-1;                             //认为在r[1]和r[i-1]之间已经有序
     low=1;
     while(low<=high)                      //对有序表进行折半查找
     {
      mid=(low+high)/2;
      if(L->INT[0]<L->INT[mid])
       high=mid-1;
      else
       low=mid+1;
     }
     for(j=i-1;j>=high+1;--j)
      L->INT[j+1]=L->INT[j];
     L->INT[high+1]=L->INT[0];
    }
}
void SHELL(SqList *L)                            //希尔排序
{
 int i,j,d;
 d=L->length/2;                               //d为增量
 while(d>=1)                                  //最后一次的增量一定为1
 {
  for(i=d+1;i<=L->length;i++)
  {
   L->INT[0]=L->INT[i];
   j=i-d;
   while(L->INT[j]>L->INT[0]&&j>0)
   {
    L->INT[j+d]=L->INT[j];
    j=j-d;
   }
   L->INT[j+d]=L->INT[0];
  }
  d=d/2;
 }
}
void QUICK(SqList *L,int low,int high)           //快速排序
{
 int i,j,temp;
 i=low;
 j=high;
 temp=L->INT[low];                            //以INT[0]为基准
 while(i<j)                                   //从两端往中间进行扫描直到i=j为止
 {
  while(i<j&&temp<=L->INT[j])              //右端进行扫描
   j--;
  if(i<j)
  {
   L->INT[i]=L->INT[j];
   i++;
  }
  while(i<j&&L->INT[i]<=temp)              //左端进行扫描
   i++; 
  if(i<j)
  {
   L->INT[j]=L->INT[i];
   j--;
  }
 }
 L->INT[i]=temp;
 if(low<i)
  QUICK(L,low,i-1);                        //对左区间进行排序
 if(i<high)
  QUICK(L,j+1,high);                       //对右区间进行排序
}
void SELECT(SqList *L)                           //选择排序
{
 int i,j,small;
 for(i=1;i<=L->length-1;i++)                  //做第i趟排序(1≤i≤length-1)
 {
  small=i;                                 //保存小址
  for(j=i+1;j<=L->length;j++)              //在当前无序区INT[i..length]中选最小的记录INT[small]
  {
   if(L->INT[j]<L->INT[small]) 
    small=j;                         //small记下目前找到的最小关键字所在的位置
  }
  if(small!=i)                             //交换值
  {L->INT[0]=L->INT[i];L->INT[i]=L->INT[small];L->INT[small]=L->INT[0];}
 }
}
void BUBBLE(SqList *L)                           //冒泡优化排序
{
 int i,j,flag=1;                              //i为扫描次数,flag标记为是否交换
 for(i=0;i<=L->length-1&&flag==1;i++)
 {
  flag=0;
  for(j=0;j<L->length-i;j++)
  {
   if(L->INT[j]>L->INT[j+1])
   {
    flag=1;
    L->INT[0]=L->INT[j];
    L->INT[j]=L->INT[j+1];
    L->INT[j+1]=L->INT[0];
   }
  }
 }
}
void BUILDHEAP(SqList *L,int k,int m)            //建立堆
{
 int i,x;
 x=L->INT[k];
 for(i=2*k;i<=m;i=i*2)
 {
  if(i<m&&L->INT[i]<L->INT[i+1])
   i++;
  if(x>L->INT[i]) break;                   //x应插入在位置k上
  L->INT[k]=L->INT[i];
  k=i;
 }
 L->INT[k]=x;                                 //插入
}
void HEAPSORT(SqList *L)                         //堆排序
{
 int i,n,temp;
 n=L->length;
 for(i=n/2;i>0;i--)
  BUILDHEAP(L,i,n);
 for(i=n;i>1;i--)
 {
  temp=L->INT[1];
  L->INT[1]=L->INT[i]; 
  L->INT[i]=temp;   
  BUILDHEAP(L,1,i-1);                      //将INT[1..n-1] 重新调整为大顶堆
 }
}
void RAND(SqList *L)                             //随机生成数字
{
 int i;
 L->length=(rand()%(14))+2;                   //长度<=15,数值>=2的随机数
 for(i=0;i<L->length;i++)
 {
  //rand((unsigned)time(NULL));            //长度为65535以内的随机数
  L->INT[i]=(rand()%(100))+1;              //为0-100的随机数   
 }
}
void INIT(SqList *L)                             //初始化排序的数据
{
 int i;
 char c;
loop:;
 TIME();
 printf("\t　       ─────────────────────\n");
 printf("\n\t\t\t请输入待排序数据的数量【>=2】: ");
 while (scanf("%d", &L->length)!=1)           //检测是否为正确输入数
 {
  while ((c=getchar())!='\n');
  printf("\n\t\t【×】Error:错误的输入,请按任意键重新输入→\n\t\t\t\t");
  getch();
  system("cls");
  goto loop;
 }
 if(L->length<2||L->length>MAXSIZE)
 {
  printf("\n\t\t\t\t 【×】Error:\n\t\t待排序数据数目小于2或超出最大输入量,请按任意键重新输入→\n\t\t\t\t");
  getch();
  system("cls");
  goto loop;
 }
 printf("\n");
 for(i=1;i<=L->length;i++)
 {

   printf("\t\t\t    请输入第%d个数据: ",i);
lable:;  
   while (scanf("%d",&L->INT[i])!=1)          //检测是否为正确输入数
   {
    while ((c=getchar())!='\n');
    printf("\n【×】Error:数据输入出错,请重新输入→");
    goto lable;
   }
 }
 printf("\n\n\n\n\t\t\t数据初始化成功,按任意键继续→\n");
 getch();
 system("cls");
}
void PRIN()                                      //格式化输出─
{
 int i;
 printf("\t\t");
 for(i=0;i<L.length;i++)
  printf("──");
 printf("\n");
}
int MENUE()
{
 int input_data;
 char c;
 TIME();
 printf("\t　     ╭─────────────────────╮\n");
    printf("\t       ｜          各种排序的基本操作实现          ｜\n");
    printf("\t　     ｜─────────────────────｜\n");
    printf("\t       ｜          1、手动(Hand)输入数据           ｜\n");
    printf("\t　     ｜─────────────────────｜\n");
 printf("\t       ｜          2、随机(Rand)生成数据           ｜\n");
    printf("\t　     ｜─────────────────────｜\n");
    printf("\t       ｜          3、退         出  ...           ｜\n");
    printf("\t       ╰─────────────────────╯\n");
 printf("\t                        请正确选择:");
 while(scanf("%d", &input_data)!=1)                  //检测是否为正确输入数
 {
  while ((c=getchar())!='\n');
  return input_data;
 }
 fflush(stdin);
 return input_data;
}
void SUB_MENUE()
{
 char c;
 for(;;){
 TIME();
    printf("\t　     ╭─────────────────────╮\n");
    printf("\t       ｜          各种排序的基本操作实现          ｜\n");
    printf("\t　     ｜─────────────────────｜\n");
    printf("\t       ｜          1、重新(Again)输入数据          ｜\n");
    printf("\t       ｜          2、折半(Binary)排序             ｜\n");
    printf("\t       ｜          3、直接(Straight)排序           ｜\n");
 printf("\t       ｜          4、希尔(Shell)排序              ｜\n");
 printf("\t       ｜          5、快速(Quick)排序              ｜\n");
 printf("\t       ｜          6、选择(Select)排序             ｜\n");
 printf("\t       ｜          7、冒泡(Bubble)排序             ｜\n");
 printf("\t       ｜          8、堆  (Heap)排序               ｜\n");
 printf("\t       ｜          9、随机(Rand)生成               ｜\n");
    printf("\t       ｜          Q、退     出  ...               ｜\n");
    printf("\t       ╰─────────────────────╯\n");
 printf("\t        【共%d个数据】如下:\n",L.length);
 PRIN();
 PRINT(&L);
 PRIN();
    printf("\t                        请选择:");
    scanf("%s",&c);
 switch(c)
 {
  case '1':
   system("cls");
   INIT(&L);
   system("cls");
   break;
  case '2':
   BIS_INT(&L);
   printf("\n\t\t\t         排序成功!!!\n\t\t\t    ");
   system("pause");
   system("cls");
   break;
  case '3':
   STINSORT(&L);
   printf("\n\t\t\t         排序成功!!!\n\t\t\t    ");
   system("pause");
   system("cls");
   break;
  case '4':
   SHELL(&L);
   printf("\n\t\t\t          排序成功!\n\t\t\t     ");
   system("pause");
   system("cls");
   break;
  case '5':
   QUICK(&L,1,L.length);
   printf("\n\t\t\t          排序成功!\n\t\t\t     ");
   system("pause");
   system("cls");
   break;
  case '6':
   SELECT(&L);
   printf("\n\t\t\t          排序成功!\n\t\t\t     ");
   system("pause");
   system("cls");
   break;
  case '7':
   BUBBLE(&L);
   printf("\n\t\t\t          排序成功!\n\t\t\t    ");
   system("pause");
   system("cls");
   break;
  case '8':
   HEAPSORT(&L);
   printf("\n\t\t\t           排序成功!\n\t\t\t    ");
   system("pause");
   system("cls");
   break;
  case '9':
   RAND(&L);
   printf("\n\t\t\t         随机生成成功!\n\t\t\t   ");
   system("pause");
   system("cls");
   break;
  case 'q':
  case 'Q':
   system("cls");
   printf("\n\n\n\n\t\t\t   谢 谢 使 用 , 再 见!!!\n");
   printf("\n\t\t\t     任 意 键 退 出!\n\t\t\t");
   getch();
   exit(0);
   break;
  default :
   printf("\n\t\t\t\t 【×】Error:\n\t\t\t  输入有误,请重新选择!!!\n");
   getch();
   system("cls");
   break;
 }
 }
}
void main(void)
{ 
 int input_data;
 //kbhit();
 //puts("输入任意字符继续:"); 
 //while (!kbhit()) /* do nothing */ ; 
 //puts("\r\n你按下了一个键!\r\n");
 do
 {
  input_data=MENUE();
  switch(input_data)
  {
  case 1:
   system("cls");
   INIT(&L);
   SUB_MENUE();  
   break;
  case 2:
   system("cls");
   RAND(&L);
   SUB_MENUE();  
   break;
  case 3:
   system("cls");
   printf("\n\n\n\n\t\t\t   谢 谢 使 用 , 再 见!!!\n");
   printf("\n\t\t\t     任 意 键 退 出!\n\t\t\t");
   getch();
   exit(0);
   break;
  default:
   printf("\n\t\t\t\t 【×】Error:\n\t\t\t  输入有误,请重新选择!!!\n");
   getch();
   system("cls");
   break;
  }
 }while(input_data!=3); 
}