#include <stdio.h>#include <stdlib.h>#include <conio.h>#define MAX_NUM 32768typedef int ElemType;//元素类型typedef struct{ ElemType key;} KeyType;//关键字的类型typedef struct{ KeyType R[MAX_NUM+1]; int length;}*orderList,Node;int compareTimes;//比较次数int moveTimes;//移动次数orderList init_orderList(){ orderList l=(orderList)malloc(sizeof(Node)); l->length=0; // printf("顺序表初始化成功"); return l;}//随机产生一些数字int produce_randomNum(orderList l){ srand(time(0)); int n,m,a,i; printf("随机产生1-m范围的 n个数:\n"); scanf("%d %d",&m,&n);//产生n个1-m之间的数字 for(i=1; i<=n; i++) { a=rand()%m+1; //printf("%d ",a); l->R[++l->length].key=a; } return n;}//打印所有数字void print_orderList(orderList l){ int i; for(i=1; i<=l->length; i++) printf("%d ",l->R[i].key); printf("\n");}//逆序void reverse(orderList l){ int i; orderList l1=init_orderList(); for(i=1; i<=l->length; i++) l1->R[i].key=l->R[i].key; for(i=1; i<=l->length; i++) { l->R[i].key=l1->R[l->length-i+1].key; // printf("%d ",l1->R[i].key); } //printf("逆序输出:\n"); //print_orderList(l);}//插入排序ElemTypevoid insertSort(orderList l){ int i,j; int signal; compareTimes=moveTimes=0; for(i=2; i<=l->length; i++) //从第二个数开始依次与前面的数字比较 { signal=l->R[i].key;//当前结点作为标志结点 j=i-1; while(j>=1)//从当前结点下一个开始与标志结点比较 { compareTimes++; if(l->R[j].key>signal)//大于标志结点,结点后移 { moveTimes++; l->R[j+1]=l->R[j]; j--; } if(l->R[j].key<=signal)//小于标志结点,结束 break; } moveTimes++; l->R[j+1].key=signal;//第j+1个结点标志结点 } printf("插入排序结果:\n"); print_orderList(l); printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);}//希尔排序void shellSort(orderList l){ compareTimes=moveTimes=0; int gap,i,j; ElemType temp; for(gap=l->length/2; gap>0; gap/=2) { for(i=gap; i<=l->length; i++) //从每组最后开始进行插入排序 { j=i; temp=l->R[j].key;//标志为当前组的最后一个 while(j-gap>=1&&l->R[j-gap].key>temp)//j-gap为本组前一个数,本组还有数字并且本组当前数字大于标志数 { compareTimes++; l->R[j]=l->R[j-gap]; moveTimes++; j=j-gap; } compareTimes++; //本组当前数字小于标志数字 l->R[j].key=temp; moveTimes++; } } printf("希尔排序结果:\n"); print_orderList(l); printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);}//冒泡排序void buddleSort(orderList l){ compareTimes=moveTimes=0; int i,j,flag; KeyType temp; for(i=1; i<=l->length-1; i++) { flag=0; for(j=1; j<=l->length-i; j++) { compareTimes++; if(l->R[j+1].key<l->R[j].key)从最后一个数开始，比较相邻两个数的位置，如果第二个数小，就交换位置,这样一次循环后最小的就会被交换到最前面 { moveTimes++; temp=l->R[j]; l->R[j]=l->R[j+1]; l->R[j+1]=temp; flag=1; } } if(flag==0) break;//没有发生交换,则提前终止 } printf("冒泡排序结果:\n"); print_orderList(l); printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);}//快速排序void quickSort(orderList l,int left,int right){ if(left>=right)//当左区间>=区间时，一部分的排序完成 { return; } int i=left,j=right; int pivotKey=l->R[left].key;//把第一个数作为一个枢纽 while(i<j) { while(i<j&&l->R[j].key>=pivotKey)//从最后一个数开始依次与枢纽比较 { compareTimes++; j--; } compareTimes++; l->R[i].key=l->R[j].key;//把比枢纽小的元素交换到低端 moveTimes++; while(i<j&&l->R[i].key<=pivotKey) { compareTimes++; i++; } compareTimes++; l->R[j].key=l->R[i].key;//把比枢纽大的交换到高端 moveTimes++; } l->R[i].key=pivotKey;// 当前元素变成枢纽元素 moveTimes++; quickSort(l,left,i-1);//枢纽左面的数形成左区间，里面的数都比枢纽小 quickSort(l,i+1,right);//枢纽右面的数字形成右区间，里面的书都比枢纽大 //对左右两部分分别进行快速排序}void selectSort(orderList l){ int i,j,min,temp; compareTimes=moveTimes=0; for(i=1; i<=l->length-1; i++) { min=i; for(j=i+1; j<=l->length; j++) { if(l->R[j].key<l->R[min].key) { min=j; compareTimes++; moveTimes++; } compareTimes++; } if(min!=i) { temp=l->R[i].key; l->R[i].key=l->R[min].key; l->R[min].key=temp; moveTimes++; } compareTimes++; } printf("简单选择排序结果:\n"); print_orderList(l); printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);}void heapAdjust(orderList l,int par,int length){ int temp=l->R[par].key; //保存当前父节点 int child=2*par; while(child<=length) { if(child+1<length&&l->R[child+1].key>l->R[child].key)//有右结点并且右结点小于左结点 child++; compareTimes++; if(temp>=l->R[child].key)//父节点如果已经大于孩子结点,提前结束 break; compareTimes++; l->R[par].key=l->R[child].key;//否则，把孩子结点的值赋给父结点 moveTimes++; //选取孩子结点左结点，继续向下筛选 par=child; child=2*par; } l->R[par].key=temp; //恢复原来的父结点}void heapSort(orderList l){ int i,j,temp; compareTimes=moveTimes=0; for(i=l->length/2; i>=1; i--) heapAdjust(l,i,l->length); for(i=l->length; i>=1; i--) { temp=l->R[i].key; l->R[i].key=l->R[1].key; l->R[1].key=temp; moveTimes++; heapAdjust(l,1,i); } printf("堆排序结果:\n"); print_orderList(l); printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes);}int main(){ /* orderList l=init_orderList(); int n=produce_randomNum(l);*/ int choice; orderList l; int n; while(1) { printf("\t\t\t\t**************排序****************\n"); printf("\t\t\t\t* *\n"); printf("\t\t\t\t* 1.初始化数据 *\n"); printf("\t\t\t\t* 2.直接插入排序 *\n"); printf("\t\t\t\t* 3.希尔排序 *\n"); printf("\t\t\t\t* 4.冒泡排序 *\n"); printf("\t\t\t\t* 5.快速排序 *\n"); printf("\t\t\t\t* 6.简单选择排序 *\n"); printf("\t\t\t\t* 7.堆排序 *\n"); printf("\t\t\t\t* 8.打印数据 *\n"); printf("\t\t\t\t* 9.逆序输出 *\n"); printf("\t\t\t\t* *\n"); printf("\t\t\t\t* 0.退出 *\n"); printf("\t\t\t\t**********************************\n"); printf("请选择(0-6):\n"); scanf("%d",&choice); switch(choice) { case 1: l=init_orderList(); n=produce_randomNum(l); break; case 2: insertSort(l);//直接插入排序 getch(); printf("正序:\n"); reverse(l); insertSort(l); getch(); printf("逆序:\n"); reverse(l); insertSort(l); break; case 3: shellSort(l);//希尔排序 getch(); printf("正序:\n"); shellSort(l);//希尔排序 getch(); printf("逆序:\n"); reverse(l); shellSort(l);//希尔排序 break; case 4: buddleSort(l);//冒泡排序 break; case 5://快速排序 compareTimes=moveTimes=0; quickSort(l,1,n); printf("快速排序结果:\n"); print_orderList(l); printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes); compareTimes=moveTimes=0; getch(); printf("正序:\n"); quickSort(l,1,n); printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes); compareTimes=moveTimes=0; getch(); printf("逆序:\n"); reverse(l); quickSort(l,1,n); printf("比较次数%d ,移动次数:%d\n",compareTimes,moveTimes); break; case 6: //选择排序 selectSort(l); break; case 7: //堆排序 heapSort(l); getch(); printf("正序:\n"); heapSort(l); getch(); printf("逆序:\n"); reverse(l); heapSort(l); break; case 8: //打印数字 print_orderList(l); break; case 9: //逆序输出数字 reverse(l); break; case 0: //退出 exit(0); default: printf("您输入的数据有误,请重新输入\n"); break; } printf("请按任意键继续\n"); getch(); system("cls"); continue; } return 0;}
た 入场券
你的名字
ゞ 浴缸里的玫瑰
爱被打了一巴掌
还没有评论，来说两句吧...