各种排序算法的实现代码

#include"stdio.h"#include"malloc.h"#include"stdlib.h"typedef int KeyType;#define MAXSIZE 20typedef struct{KeyType key;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList,* SQLIST;void play_choose(void);//显示菜单void creat_list(SQLIST L) ;//创建顺序表void traverse_list(SQLIST L);//遍历顺序表int Search_Seq(SQLIST L,KeyType key);//顺序查找void InsertSort(SQLIST L);//直接插入排序法int Search_Bin(SQLIST L,KeyType key);//折半查找void QSort(SQLIST L,int low,int high);//递归形式的快排int Partition(SQLIST L,int low,int high);//递归形式的快排的一趟快排执行代码void SelectSort(SQLIST L);//简单排序法void Effervesce(SQLIST L);//冒泡排序void BInsertSort(SQLIST L);//折半插入排序void main(){int i;int key=67,sum,sum1; SQLIST L; L=(SQLIST)malloc(sizeof(SqList));if(L==NULL){printf("动态内存分配失败！");exit(-1);} play_choose();//显示菜单while(true){ printf("\n\t请选择你要执行的操作："); scanf("%d",&i); switch(i)//实现用户选择操作{ case 1:creat_list(L);break;//创建顺序表 case 2:printf("\n\t请选择你要查找的关键字的值：");//顺序查找 scanf("%d",&key); sum=Search_Seq(L,key);if(sum!=0){ printf("\n\t你要查找的关键字的值与第%d个元素相等\n",sum) ;}else{printf("\n你要查找的关键字不存在\n");}break; case 3: InsertSort(L);traverse_list(L);break;//直接插入排序法 case 4: QSort(L,1,L->length);traverse_list(L);break;//递归形式的快排 case 5:SelectSort(L);traverse_list(L);break;//简单排序法 case 6:Effervesce(L);traverse_list(L);break;//冒泡排序 case 7: BInsertSort(L);traverse_list(L);break;//折半插入排序 case 8: printf("\n\t请选择你要查找的关键字的值：");//折半查找 scanf("%d",&key); Search_Bin(L,key); sum1=Search_Bin(L,key); if(sum1!=0){ printf("\n\t你要查找的关键字的值与第%d个元素相等\n",sum1) ;}else{printf("\n\t你要查找的关键字不存在\n");}break; case 9: play_choose();traverse_list(L);break;//清屏显示菜单 case 0:exit(-1);//退出 default: printf("\t您输入的是非法值\n"); break;}}}void play_choose(void){system("cls");printf("\n\n\n\t\t…………………………………\n\n\n");printf("\t\t 1-建立顺序表 2-顺序查找 \n\n");printf("\t\t 3-直接插入排序 4-快速排序 \n\n");printf("\t\t 5-简单选择排序 6-冒泡排序 \n\n");printf("\t\t 7-拆半插入排序 8-折半查找 \n\n");printf("\t\t 9-清屏显示菜单 0-退出 \n\n");printf("\n\n\t\t………………………………… \n\n\n");}void creat_list(SQLIST L)//创建顺序表{int i;int val;int len;printf("请输入你要建立的顺序表的长度（第一个位置不存储元素）：");scanf("%d",&len);for(i=1;i<=len;i++){printf("\t请输入第%d个元素的值：",i);scanf("%d",&val);L->r[i].key=val;}L->length=len;printf("\n");printf("\t\t\t恭喜您建表成功\n");}void traverse_list(SQLIST L)//遍历顺序表{printf("\t\t处理后的数据： ");int i;for(i=1;i<=L->length;i++){printf("%d ",L->r[i].key);}printf("\n");}int Search_Seq(SQLIST L,KeyType key)//顺序查找{int i; L->r[0].key=key; for(i=L->length;L->r[i].key!=key;i–); return i;}void InsertSort(SQLIST L)//直接插入排序法{int j,i; for(i=2;i<=L->length;i++) { if(L->r[i].key < L->r[i-1].key) { L->r[0]=L->r[i]; L->r[i]=L->r[i-1]; for(j=i-2;L->r[0].key<L->r[j].key;j–) { L->r[j+1]=L->r[j]; } L->r[j+1]=L->r[0]; } }}int Search_Bin(SQLIST L,KeyType key)//折半查找{ int low=1; int high=L->length; int mid; while(low<=high) { mid=(low+high)/2; if( key==L->r[mid].key) return mid; else if(key<L->r[mid].key) high=mid-1; else low=mid+1; } return 0;}void QSort(SQLIST L,int low,int high)//递归形式的快排{intpivotloc;if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}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];while(low<high && L->r[low].key<=pivotkey) ++low; L->r[high]=L->r[low];} L->r[low]=L->r[0];return low;}void SelectSort(SQLIST L)//简单排序法{int k,i,j;for(i=1;i<=L->length;++i){j=i;for(k=i+1;k<=L->length;k++){if(L->r[k].key<L->r[j].key){j=k;}}if(i!=j){ RedType k=L->r[i]; L->r[i]=L->r[j]; L->r[j]=k;}}}void Effervesce(SQLIST L)//冒泡排序{int i,j;for(i=1;i<L->length;i++){for(j=1;j<=L->length-i;j++){if(L->r[j].key>L->r[j+1].key){ RedTypetemp=L->r[j];L->r[j]=L->r[j+1];L->r[j+1]=temp;}}}}void BInsertSort(SQLIST L)//折半插入排序{int i,j,mid;int low,high;for(i = 2;i <= L->length;i++){L->r[0]=L->r[i];low =1;high = i-1;while(low <= high){mid = (low+high)/2;if(L->r[0].key < L->r[mid].key)high = mid-1;elselow = mid+1;}for(j = i-1;j >=high+1;j–)L->r[j+1]=L->r[j];L->r[high+1] = L->r[0];}}

，人生难免遇风雨,天空晴朗有阴云,别因雨水湿透衣衫而难过,

相关文章：

你感兴趣的文章：

标签云：