paixubijiao.txt

1. 内部排序演示 问题描述 设计一个测试程序比较几种排序算法的关键字比较次数和移动次数以取得直观感受。 基本要求 （1）对起（冒）泡排序、直接插入排序、简单选择排序、快速排序、希尔

⑴插入排序。 
⑵交换排序。 
⑶选择排序。 
⑷归并排序。 
⑸基数排序。







#define MAXSIZE 20 
#define LT(a,b) ((a)<(b)) 
typedef int KeyType; 
typedef int InfoType; 
typedef struct{ 
KeyType key; 
InfoType otherinfo; 
}RedType; 
typedef struct{ 
RedType r[MAXSIZE+1]; 
int length; 
}SqList; 
//typedef RedType TESTLIST[20]; 

void InsertSort(SqList *L) 
{ 
int i,j; 
for(i=2;i<=L->length;++i) 
if(LT(L->r[i].key,L->r[i-1].key)){//if bigger,put it there,else: 
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]; //move to the back place 
L->r[j+1]=L->r[0]; //move to the right place 
} 
} 

void BInsertSort(SqList *L) 
{ 
int i,j; 
int low,high,m; 
for(i=2;i<=L->length;++i){ 
L->r[0]=L->r[i]; 
low=1;high=i-1; 
while(low<=high){ 
m=(low+high)/2; 
if (LT(L->r[0].key,L->r[m].key)) 
high=m-1; 
else low=m+1; 
} 
for(j=i-1;j>=high+1;--j) 
L->r[j+1]=L->r[j]; 
L->r[high+1]=L->r[0]; 
} 
} 

/* QuickSort related function */ 
int Partition(SqList *L,int low,int high) 
{ 
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; 
L->r[low]=L->r[high];//find the first value of r[high].key<pivotkey 
while(low<high&&L->r[low].key<=pivotkey) ++low; 
L->r[high]=L->r[low];//find the first value of r[low].key>pivotkey 
} 
L->r[low]=L->r[0]; 
return low; 
} 
void QSort(SqList *L,int low,int high) 
{ 
int pivotloc; 
if(low<high){ 
pivotloc=Partition(L,low,high); 
QSort(L,low,pivotloc-1); 
QSort(L,pivotloc+1,high); 
} 
} 
void QuickSort(SqList *L) 
{ 
QSort(L,1,L->length); 
} /* End QuickSort related function*/ 

/*SelectSort related function */ 
int SelectMinKey(SqList L,int i) 
{ 
int k; 
int j; 
k=i; 
for(j=i;j<L.length+1;j++) 
if(L.r[k].key>L.r[j].key) 
k=j; 
return k; 
} 
void SelectSort(SqList *L) 
{ 
RedType t; 
int i,j; 
for(i=1;i<L->length;++i){ 
j=SelectMinKey(*L,i); 
if(i!=j) { 
t=L->r[i]; 
L->r[i]=L->r[j]; 
L->r[j]=t; 
} 
} 
} /*End SelectSort related function */ 


typedef SqList HeapType; 
void HeapAdjust(HeapType *H,int s,int m) 
{ 
RedType rc; 
int j; 
rc=H->r[s]; 
for(j=2*s;j<=m;j*=2){ 
if(j<m&<(H->r[j].key,H->r[j+1].key)) ++j; 
if(!LT(rc.key,H->r[j].key)) break; 
H->r[s]=H->r[j]; 
s=j; 
} 
H->r[s]=rc; 
} 
void HeapSort(HeapType *H) 
{ 
RedType t; 
int i; 
for(i=H->length/2;i>0;--i) 
HeapAdjust(H,i,H->length); 
for(i=H->length;i>1;--i){ 
t=H->r[1]; 
H->r[1]=H->r[i]; 
H->r[i]=t; 
HeapAdjust(H,1,i-1); 
} 
} 

void BubbleSort(SqList *R) 
{ 
int i,j; 
int exchange; 
int n = R->length; 
for(i=1;i<n;i++){ 
exchange=0; 
for(j=n-1;j>=i;j--) 
if(/*R[j+1].key<R[j].key */LT(R->r[j+1].key,R->r[j].key)){ 
R->r[0]=R->r[j+1]; 
R->r[j+1]=R->r[j]; 
R->r[j]=R->r[0]; 
exchange=1; 
} 
if(!exchange) 
return; 
} 
} 

main() 
{ 

int a[]={44,33,66,99,88,77,11,22,55}; 
int i,k; 
SqList s; 

printf("\nThe record to be sort:\n"); 
for(i=1;i<9;i++) 
{ 
s.r[i].key=a[i-1]; 
printf("%d ",a[i-1]); 
} 
s.length=i-1; 
printf("\n\t1,InsertSort\n\t2,BInsertSort\n\t3,QuickSort\n\t4,SelectSort\n"); 
printf("\t5,HeapSort\n\t6,BubbleSort\nPress a number among 1-5 to select a function\n"/* 134 is important!\n*/); 
scanf("%d",&k); 
switch(k){ 
case 1: 
InsertSort(&s); 
break; 
case 2: 
BInsertSort(&s); 
break; 
case 3: 
QuickSort(&s); 
break; 
case 4: 
SelectSort(&s); 
break; 
case 5: 
HeapSort(&s); 
break; 
case 6: 
BubbleSort(&s); 
break; 
default:printf("No function which you select.\n"); 
} 
printf("\nThe records be sorted:\n"); 
for(i=1;i<9;i++) 
printf("%d ",s.r[i].key); 
printf("\n\n\tPress any key to exit.\n"); 
getch(); 
}