实现直接插入、简单选择排序和快速排序
实现直接插入、简单选择排序和快速排序，并比较各种排序算法的运行速度。
要求:(1) 采用顺序表存放待排序的记录，设关键字类
型为整型。
程序代码：#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;
}
}
}
int 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);
}
同意楼上的说法