//只有计算交换和比较次数的程序
//利用随机函数产生1000个随机整数，
//利用插入排序、起泡排序、快速排序、选择排序、堆排序、

#include
#include
#include
#define LS(a,b) ((a)<(b))
#define LL(a,b) ((a)>(b))
#define MAXSIZE 1000
typedef int KeyType;
typedef struct
{
int key;
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}SqList;
typedef SqList HeapType;
int compare=0;
int change=0;
int Create_Sq(SqList &L)
{
int i,k;
cout<<"请输入产生随机数的个数:";
cin>>k;
L.length=k;
for(i=1;i<=k;++i)
{

L.r[i].key=rand();
}
return 1;
}
void Bubble_sort(SqList &L)
{//冒泡排序
int i,j,l,k=L.length;
for(i=1;i<=L.length-1;++i)
{
for(j=1;j<=k-1;++j)
{
++compare;
if(LL(L.r[j].key,L.r[j+1].key))
{
l=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=l;
++change;
}
}
–k;
}
cout< for(i=1;i<=L.length;i++)
cout<<" "< cout< cout<<"冒泡排序的比较次数:";
cout< cout<<"冒泡排序的交换次数:";
cout< compare=0;
change=0;
}
void InsertSort(SqList &L)
{//直接插入排序
int i,j;
cout< for(i=2;i<=L.length;++i)
if(LS(L.r[i].key,L.r[i-1].key))
{
++compare;
++change;
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
for(j=i-2;LS(L.r[0].key,L.r[j].key);–j)
{
++compare;
L.r[j+1]=L.r[j];
}
L.r[j+1]=L.r[0];
}
cout<<"—–直接插入排序后的序列—–"< for(i=1;i<=L.length;i++)
cout<<" "< cout< cout<<"直接插入排序的比较次数:";
cout< cout<<"直接插入排序的交换次数:";
cout< compare=0;
change=0;
}
void SelectSort(SqList &L)
{//简单选择排序
int l,i,j;
cout< for(i=1;i {
L.r[0]=L.r[i];
j=i+1;
l=i;
for(j;j<=L.length;++j)
{
++compare;
if(LL(L.r[0].key,L.r[j].key))
{
l=j;
L.r[0]=L.r[j];
}
}
if(l!=i)
{
++change;
L.r[l]=L.r[i];
L.r[i]=L.r[0];
}
}
cout<<"—–简单选择排序后的序列—–"< for(i=1;i<=L.length;i++)
cout<<" "< cout< cout<<"简单选择排序的比较次数:";
cout< cout<<"简单选择排序的交换次数:";
cout< compare=0;
change=0;
}
int Partition(SqList &L,int low,int high)
{
int pivotkey;
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(low {
while(low=pivotkey)
{
++compare;
–high;
}
++change;
L.r[low]=L.r[high];
while(low {
++compare;
++low;
}
++change;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void QSort(SqList &L,int low,int high)
{//递归形式的快速排序算法
int pivotloc;
if(low {
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L)
{
int i;
QSort(L,1,L.length);
cout<<"—–快速排序后的序列为—–"< for(i=1;i<=L.length;i++)
cout<<" "< cout< cout<<"快速排序的比较次数:";
cout< cout<<"快速排序的交换次数:";
cout< compare=0;
change=0;
}

void HeapAdjust(HeapType &H,int s,int m)
{//堆排序
int j;
RedType rc;
rc=H.r[s];
for(j=2*s;j<=m;j*=2)
{
if(j {
++compare;
++j;
}
if(!LS(rc.key,H.r[j].key))
{
++compare;
break;
}
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc;
}
void HeapSort(HeapType &H)
{
int i;
for(i=H.length/2;i>0;–i)
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;–i)
{
++change;
H.r[0]=H.r[1];
H.r[1]=H.r[i];
H.r[i]=H.r[0];
HeapAdjust(H,1,i-1);
}
cout<<"—–堆排序后的序列为—–"< for(i=1;i<=H.length;i++)
cout<<" "< cout< cout<<"堆排序的比较次数:";
cout< cout<<"堆排序的交换次数:";
cout< compare=0;
change=0;
}

void main()
{
int i;
int dlta[MAXSIZE];
SqList L;
Create_Sq(L);

cout<<"—–待排序序列为—–"< for(i=1;i<=L.length;i++)
cout<<" "<


//冒泡排v序
SqList L1=L;
Bubble_sort(L1);
//直接插入排序
SqList L2=L;
InsertSort(L2);
//简单选择排序
SqList L3=L;
SelectSort(L3);
//快速排序
SqList L4=L;
QuickSort(L4);

//堆排序
SqList L6=L;
HeapSort(L6);
}