关于五种排序的比较和移动问题
实验目的熟练掌握各种排序算法的实现方法，以及不同算法的特点，掌握各种排序方法的时间效率。
时间要求：4+4学时
问题描述：
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。对一组给定的数据，设计出各不同排序算法对其进行排序，给出各算法在排序中的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：
（1）对以下各排序算法进行比较：直接插入排序、冒泡排序、快速排序、简单选择排序、归并排序。
（2）待排序表的表长为100；一共有n组不同的数据，对每组数据用以上各排序方法进行排序，比较的指标为有关键字参加的比较次数和关键字的移动次数。
实现提示：
在算法的适当地方加入计数操作，计算关键字的比较次数和移动次数。
选作内容：
对算法的稳定性作验证。
Input
输入部分第一行为待排关键字的组数n，接下来为n行待排关键字，第行有100个整数所有数据之间由空格分隔。
Output
输出共n行，每行共有10个整数，表示5种排序方法排序的关键字比较次数和移动次数，即为：直接插入排序比较次数 直接插入排序移动次数 冒泡排序比较次数 冒泡排序移动次数 快速排序比较次数、快速排序移动次数 简单选择排序比较次数、简单选择排序移动次数 归并排序比较次数 归并排序移动次数
（下例待排关键字为5，实际提交测试数据为100）
Sample Input
3
1 2 3 4 5
5 4 3 2 1
4 2 5 1 3
Sample Output
4 0 4 0 10 16 10 0 7 12
14 18 10 30 12 16 10 6 5 12
10 12 10 18 11 14 10 6 7 12
程序代码：#include<stdio.h>
#include <malloc.h>
#define MAXSIZE 100
typedef struct
{
int key;
}RedType;//记录类型
typedef struct
{
RedType r[MAXSIZE + 1];
int length;
}SqList;
int LT(int a,int b)
{
if(a <= b)
return 1;
return 0;
}
//直接插入排序
void InsertSort(SqList *L,int *compare,int *move)
{ /* 对顺序表L作直接插入排序。算法10.1 */
int i,j;
(*compare) = 0;
(*move) = 0;
for(i=2;i<=(*L).length;++i)
{
if (LT((*L).r[i].key,(*L).r[i-1].key) )/* "<",需将L.r[i]插入有序子表 */
{
//(*compare)++;//a1
(*L).r[0]=(*L).r[i]; /* 复制为哨兵 */
(*move)++;
(*L).r[i]=(*L).r[i-1];//腾出位置
(*move)++;
for(j=i-2;LT((*L).r[0].key,(*L).r[j].key);--j)
{
(*L).r[j+1]=(*L).r[j]; /* 记录后移 */
(*move)++;
(*compare)++;//b1
}
(*compare)++;//b2
(*L).r[j+1]=(*L).r[0]; /* 插入到正确位置 */
//(*move)++;
}
(*compare)++;//a2
}
}
void printInsert(int r[],int n)
{
int i;
for(i=1;i<=n;i++)
printf("%d ",r[i]);
printf("\n");
}
///////////////////////////////////////////////////////////
void BubbleSort(SqList *L,int *compare,int *move)
{
int i , j;
RedType t;
(*compare) = 0;
(*move) = 0;
for(i = 1 ; i <= (*L).length - 1; i++)
{
(*compare)++;
for(j = 1 ; j <= (*L).length - i ; j++ )
{
if( (*L).r[j].key > (*L).r[j+1].key)
{
t = (*L).r[i];
(*L).r[i] = (*L).r[j];
(*L).r[j] = t;
(*move)++;
}
(*compare)++;
}
}
}
void printBubble(int r[],int n)
{
int i;
for(i=1;i<=n;i++)
printf("%d ",r[i]);
printf("\n");
}
//////////////////////////////////////////////////////////////
int Partition(SqList *L,int low,int high,int *compare,int *move)
{ /* 交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其 */
/* 所在位置，此时在它之前（后）的记录均不大（小）于它。算法10.6(b) */
int pivotkey;
(*L).r[0]=(*L).r[low]; /* 用子表的第一个记录作枢轴记录 */
pivotkey=(*L).r[low].key; /* 枢轴记录关键字 */
while(low< high)
{ /* 从表的两端交替地向中间扫描 */
while(low<high&&(*L).r[high].key>=pivotkey)
{
--high;
(*compare)++;
}
(*L).r[low]=(*L).r[high]; /* 将比枢轴记录小的记录移到低端 */
(*move)++;
while(low<high&&(*L).r[low].key<=pivotkey)
{
++low;
(*compare)++;
}
(*L).r[high]=(*L).r[low]; /* 将比枢轴记录大的记录移到高端 */
(*move)++;
}
(*L).r[low]=(*L).r[0]; /* 枢轴记录到位 */
return low; /* 返回枢轴位置 */
}
void printPartition(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}
void QSort(SqList *L,int low,int high,int *compare,int *move)
{ /* 对顺序表L中的子序列L.r[low..high]作快速排序。算法10.7 */
int pivotloc;
if(low<high)
{ /* 长度大于1 */
pivotloc=Partition(L,low,high,compare,move); /* 将L.r[low..high]一分为二 */
QSort(L,low,pivotloc-1,compare,move); /* 对低子表递归排序，pivotloc是枢轴位置 */
QSort(L,pivotloc+1,high,compare,move); /* 对高子表递归排序 */
}
}
//////////////////////////////////////////////////////////////////
///////////////////////////////////简单选择排序
int SelectMinKey(SqList L,int i,int *compare,int *move)
{ /* 返回在L.r[i..L.length]中key最小的记录的序号 */
int min;
int j,k;
k=i; /* 设第i个为最小 */
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
{
(*compare)++;
if(L.r[j].key<min) /* 找到更小的 */
{
k=j;
min=L.r[j].key;
(*move)++;
}
}
return k;
}
void SelectSort(SqList *L,int *compare,int *move)
{ /* 对顺序表L作简单选择排序。算法10.9 */
int i,j;
RedType t;
(*compare) = 0;
(*move) = 0;
for(i=1;i<(*L).length;++i)
{ /* 选择第i小的记录，并交换到位 */
j=SelectMinKey(*L,i,compare,move); /* 在L.r[i..L.length]中选择key最小的记录 */
if(i!=j)
{ /* 与第i个记录交换 */
t=(*L).r[i];
(*L).r[i]=(*L).r[j];
(*L).r[j]=t;
(*move)++;
}
}
}
void printSelect(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d)",L.r[i].key);
printf("\n");
}
////////////////////////////////////////////////
void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 */
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]。算法10.13 */
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作归并排序。算法10.14 */
MSort((*L).r,(*L).r,1,(*L).length);
}
void printMerge(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d)",L.r[i].key);
printf("\n");
}
//////////////////////////////////////////////////////////////////////
void main()
{
SqList L;
int compare,move,i;
for(i = 1 ; i <= 5 ; i++)
{
scanf("%d",&(L.r[i].key));
}
L.length = i - 1;
//printInsert(L.r,L.length);
//InsertSort(&L,&compare,&move);
//printInsert(L.r,L.length);
//printf("%d %d\n",compare,move);
printBubble(L.r,L.length);
BubbleSort(&L,&compare,&move);
printBubble(L.r,L.length);
printf("%d %d \n",compare,move);
//printBubble(L.r,L.length);
//BubbleSort(&L,&compare,&move);
//printf("%d %d\n",compare,move);
//QSort(&L,1,L.length,&compare,&move);
//printf("%d %d\n",compare,move);
//SelectSort(&L,&compare,&move);
//printf("%d %d\n",compare,move);
//MergeSort(&L);
//printMerge(L);
}
出现的问题：计算比较和移动次数错误！
