#include
#define N 8
#define MAXSIZE 20 /* 一个用作示例的小顺序表的最大长度 */
#define LT(a,b) ((a)<(b))
typedef int InfoType; /* 定义其它数据项的类型 */
typedef int KeyType; /* 定义关键字类型为整型 */
typedef struct
{
KeyType key; /* 关键字项 */
InfoType otherinfo; /* 其它数据项，具体类型在主程中定义 */
}RedType; /* 记录类型 */
typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]闲置或用作哨兵单元 */
int length; /* 顺序表长度 */
}SqList; /* 顺序表类型 */
void InsertSort(SqList *L)
{ /* 对顺序表L作直接插入排序。*/
int i,j;
for(i=2;i<=(*L).length;++i)
if LT((*L).r[i].key,(*L).r[i-1].key) /* "<",需将L.r[i]插入有序子表 */
{
(*L).r[0]=(*L).r[i]; /* 复制为哨兵 */
for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j)
(*L).r[j+1]=(*L).r[j]; /* 记录后移 */
(*L).r[j+1]=(*L).r[0]; /* 插入到正确位置 */
}
}
void bubble_sort(SqList *L)
{ /* 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序) */
int i,j;
int change;
for(i=L->length-2,change=1;i>1&&change;--i)
{
change=0;
for(j=0;j
{
(*L).r[0]=(*L).r[j];
(*L).r[j]=(*L).r[j+1];
(*L).r[j+1]=(*L).r[0];
change=1;
}
}
}
int Partition(SqList *L,int low,int high)
{ /* 交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位， */
/* 并返回其所在位置，此时在它之前(后)的记录均不大(小)于它。*/
RedType t;
KeyType pivotkey;
pivotkey=(*L).r[low].key; /* 用子表的第一个记录作枢轴记录 */
while(low
while(low
--high;
t=(*L).r[low]; /* 将比枢轴记录小的记录交换到低端 */
(*L).r[low]=(*L).r[high];
(*L).r[high]=t;
while(low
t=(*L).r[low]; /* 将比枢轴记录大的记录交换到高端 */
(*L).r[low]=(*L).r[high];
(*L).r[high]=t;
}
return low; /* 返回枢轴所在位置 */
}
void QSort(SqList *L,int low,int high)
{ /* 对顺序表L中的子序列L.r[low..high]作快速排序。*/
int pivotloc;
if(low
pivotloc=Partition(L,low,high); /* 将L.r[low..high]一分为二 */
QSort(L,low,pivotloc-1); /* 对低子表递归排序，pivotloc是枢轴位置 */
QSort(L,pivotloc+1,high); /* 对高子表递归排序 */
}
}
void QuickSort(SqList *L)
{ /* 对顺序表L作快速排序。*/
QSort(L,1,(*L).length);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
int j,k,l;
for(j=m+1,k=i;i<=m&&j<=n;++k) /* 将SR中记录由小到大地并入TR */
if LT(SR[i].key,SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++];
if(i<=m)
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; /* 将剩余的SR[i..m]复制到TR */
if(j<=n)
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; /* 将剩余的SR[j..n]复制到TR */
}
void MSort(RedType SR[],RedType TR1[],int s, int t)
{ /* 将SR[s..t]归并排序为TR1[s..t]。*/
int m;
RedType TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
MSort(SR,TR2,s,m); /* 递归地将SR[s..m]归并为有序的TR2[s..m] */
MSort(SR,TR2,m+1,t); /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
Merge(TR2,TR1,s,m,t); /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
}
}
void MergeSort(SqList *L)
{ /* 对顺序表L作归并排序。*/
MSort((*L).r,(*L).r,1,(*L).length);
}
void HeapAdjust(SqList *H,int s,int m)
{ /* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数 */
/* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */
RedType rc;
int j;
rc=(*H).r[s];
for(j=2*s;j<=m;j*=2)
{ /* 沿key较大的孩子结点向下筛选 */
if(j
if(!LT(rc.key,(*H).r[j].key))
break; /* rc应插入在位置s上 */
(*H).r[s]=(*H).r[j];
s=j;
}
(*H).r[s]=rc; /* 插入 */
}
void HeapSort(SqList *H)
{ /* 对顺序表H进行堆排序。*/
RedType t;
int i;
for(i=(*H).length/2;i>0;--i) /* 把H.r[1..H.length]建成大顶堆 */
HeapAdjust(H,i,(*H).length);
for(i=(*H).length;i>1;--i)
{ /* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */
t=(*H).r[1];
(*H).r[1]=(*H).r[i];
(*H).r[i]=t;
HeapAdjust(H,1,i-1); /* 将H.r[1..i-1]重新调整为大顶堆 */
}
}
void menu()
{
printf("\t1\t简单插入排序\n");
printf("\t2\t冒泡排序\n");
printf("\t3\t快速排序\n");
printf("\t4\t并归排序\n");
printf("\t5\t堆排序\n");
printf("\t0\t退出\n");
}
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l1;
int i,n;
do
{
for(i=0;i
l1.length=N;
printf("排序前:\n");
print(l1);
printf("选择排序方法(0退出)\n");
menu();
scanf("%d",&n);
system("cls");
switch(n)
{
case 1:{
InsertSort(&l1);
printf("简单插入排序后:\n");
print(l1);
break;
}
case 2:{
bubble_sort(&l1);
printf("冒泡排序后:\n");
print(l1);
break;
}
case 3:{
QuickSort(&l1);
printf("快速排序后:\n");
print(l1);
break;
}
case 4:{
MergeSort(&l1);
printf("并归排序后:\n");
print
(l1);
break;
}
case 5:{
HeapSort(&l1);
printf("堆排序后:\n");
print(l1);
break;
}
}
}while(n !=0);
}