#include
#include
typedef int ElemType;
#define MAX 10000
typedef struct{
ElemType *elem;
int length;
}SqList;

void InitList(SqList &L){
L.elem = (ElemType *)malloc(MAX*sizeof(ElemType));
free(L.elem);
L.elem = (ElemType *)malloc(MAX*sizeof(ElemType));
L.length = MAX;
}//初始化顺序表

void Merge(ElemType SR[],ElemType TR[],int i,int m ,int n){
int j,k;
for(j=m+1,k=i;i<=m&&j<=n;k++){
if(SR[i]<=SR[j])
TR[k]=SR[i++];
else TR[k] = SR[j++];
}
while(i<=m) TR[k++] = SR[i++];
while(j<=n) TR[k++] = SR[j++];
}// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
void Msort( ElemType SR[], ElemType TR1[], int s, int t ){
int k;
ElemType TR2[MAX];
if(s==t) TR1[s] = SR[s];
else
{
k = (s+t)/2;
Msort(SR,TR2,s,k);
Msort(SR,TR2,k+1,t);
Merge(TR2,TR1,s,k,t);
}
}// 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]
void SelectSort(SqList &L){
int i,j,k;
ElemType temp;
int n=L.length;
for(i=1;i<n;i++){
k = i;
for(j=i+1;j<=n;j++)
if(L.elem[j]<L.elem[k])
k=j;
if(i!=k){
temp = L.elem[i];
L.elem[i] = L.elem[k];
L.elem[k] = temp;
}
}
}//简单选择排序的实现

int QKPass(ElemType s[],int left,int right){
ElemType x = s[left];
while(left while(left=x){
right--;
}
if(left s[left] = s[right];
left++;
}
while(left left++;
}
if(left s[right] = s[left];
right--;
}
}
s[left] = x;
return left;
}//一趟快速排序算法
void HeapAdjust (SqList &H, int s, int m){
H.elem[0] = H.elem[s];
int j;
H.elem[0] = H.elem[s];
for(j = 2*s ; j if(j j++;
if(H.elem[0]>=H.elem[j])
break;
H.elem[s] = H.elem[j];
s = j;
}
H.elem[s] = H.elem[0];
}//保存大顶堆的根元素后，对大顶堆的调整
void HeapSort (SqList &H){
int i ;
ElemType temp;
for(i=H.length/2;i>1;i--)
temp = H.elem[0];
H.elem[0] = H.elem[H.length];
H.elem[H.length] = temp;
for(i = H.length-1;i>1;i--){
temp = H.elem[1];
H.elem[1] = H.elem[i];
H.elem[i] = temp;
}
}//建立大顶堆，实现堆排序

void BubbleSort(SqList &L){
int n = L.length,change = 1;
int i,j;
ElemType temp;
for(i=1;i change = 0;
for(j=1;j if(L.elem[i]>L.elem[j]){
temp = L.elem[i];
L.elem[i] = L.elem[j];
L.elem[j] = temp;
change = 1;
}
}
}//冒泡排序算法实现

void QKsort(ElemType s[],int low,int high){
int pos;
if(low<high){
pos = QKPass(s,low,high);
QKsort(s,low,pos-1);
QKsort(s,pos+1,high);
}
}//递归实现快序排序
void DeleteItem(SqList &L,ElemType item){
int i;
for(i=1;i<L.length;i++)
if(L.elem[i]==item){
L.elem[i] = L.elem[--L.length];
free(&L.elem[L.length]);
}
}//删除与item相同元素

int main(){
double t1,t2;
int i;
SqList L1,L2;
int k;
printf("**************************************\n");
printf("0、退出\n");
printf("1、二路归并排序\n");
printf("2、堆排序\n");
printf("3、冒泡排序\n");
printf("4、快速排序\n");
printf("5、直接插入排序\n");
printf("6、删除与Item相同元素\n");
printf("**************************************\n");
do{
InitList(L1);
InitList(L2);
scanf("%d",&k);
for(i=1;i<L1.length;i++)
L1.elem[i] = rand()%MAX;
for(i=1;i<L2.length;i++)
L2.elem[i]=i;
switch(k){
case 0:break;
case 1:
printf("\n********二路归并排序******\n");
t1=clock();
Msort(L1.elem,L1.elem,1,L1.length-1);
t1 = clock() - t1;
t2=clock();
Msort(L2.elem,L2.elem,1,L2.length-1);
t2 = clock()- t2;

``````        break;
case 2:
printf("\n**********堆排序*********\n");
t1=clock();
HeapSort(L1);
t1 = clock() - t1;
t2=clock();
HeapSort(L2);
t2=clock() - t2;

break;
case 3:
printf("\n*********冒泡排序********\n");
t1=clock();
BubbleSort(L1);
t1 = clock() - t1;
t2=clock();
BubbleSort(L2);
t2=clock() - t2;

break;
case 4:
printf("\n*********快速排序********\n");
t1=clock();
QKsort(L1.elem,1,L1.length-1);
t1 = clock() - t1;
t2=clock();
QKsort(L2.elem,1,L2.length-1);
t2=clock() - t2;

break;

case 5:
printf("\n********直接插入排序******\n");
t1=clock();
SelectSort(L1);
t1 = clock() - t1;
t2=clock();
SelectSort(L2);
t2=clock() - t2;
break;
case 6:
t1=clock();
DeleteItem(L1,5);
t1=clock()-t1;
for(i=1;i<L1.length;i++)
printf("%d ",L1.elem[i]);
break;
default :
printf("\n输入错误!\n\n");
}
if(0<k&&k<6){
printf("\n该排序无序表排序时间:%f毫秒\n",(double)t1);
printf("\n该排序有序表排序时间:%f毫秒\n\n",(double)t2);
}
else if(k==6) printf("\n删除元素的时间为%f毫秒\n",(double)t1);
}while(k!=0);

return 0;
``````

}

1个回答

csdn_liang2015 ok，谢谢！

csdn_liang2015 弱弱的问一句，哪些变量？本人比较菜，线性表是按照一般定义形式定义的，我不知道要改哪些变量。谢谢啦