21、折半插入排序21、折半插入排序21、折半插入排序21、折半插入排序

#include <dos.h> #include <conio.h> #include <math.h> #include <stdio.h> #include <stdlib.h> //===========================折半插入排序 #define MAXSIZE 100 typedef struct { int key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length; }SqList; void BInsertSort(SqList &L)//对顺序表L作折半插入查找 { int i,low,high,m,j; for(i=2;i<=L.length;++i) { L.r[0]=L.r[i];//暂存 low=1; high=i-1; while(low<=high)//在r中折半查找有序插入的位置 { m=(low+high)/2;//折半 if(L.r[0].key<L.r[m].key)//LT 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];//插入 } } //====================================冒泡查找 #define LIST_INIT_SIZE 100 #define True 1 #define False 0 #define LISTINCREMENT 10 typedef int KeyType; typedef char InfoType; typedef int ElemType; typedef struct { KeyType key; InfoType otherinfo; } RedType1; typedef struct { RedType1 r[MAXSIZE+1]; int length; } SqList1; void CreateSqList(SqList1 *L); void Bubble ( SqList1 *L ); void Bubble ( SqList1 *L ) { int i,j,k,n; i = 1; n=L->length; for(i=n;i>0;i--) for(j=1;j<i;j++)//i控制次数，越来越小 if (L->r[j].key < L->r[j+1].key) //将小的换到上面，冒泡 { k = L->r[j].key; L->r[j].key = L->r[j+1].key; L->r[j+1].key = k; } } void CreateSqList(SqList1 *L) { int i; printf("请输入将要冒泡排序的整数的个数,(大于等于1):"); scanf("%d",&(L->length)); printf("\n请输入%d 个整数,以回车或者空格作为间隔,(如 42 20 17 13 28 14 23 15) :\n",L->length); for (i=1;i<=L->length;i++) scanf("%d",&(L->r[i].key)); } //=======================================================快速查找 typedef struct {int elemword[MAXSIZE]; int count; }SqList2; void InitialSqList(SqList2&); void QuickSort(SqList2 &); void QSort(SqList2 &,int,int); int Partition(SqList2 &,int,int); void PrintSqList(SqList2); void InitialSqList(SqList2 &L) { int i; printf("请输入待排序的记录的个数:"); scanf("%d",&L.count); printf("请输入待排序的记录的关键字(整型数):\n"); for(i=1;i<=L.count;i++) scanf("%d",&L.elemword[i]); } void QuickSort(SqList2 &L) { QSort(L,1,L.count); } void QSort(SqList2 &L,int low,int high)//对顺序表L的子序列L.r[low..high]作快速排序 { int pivotloc; if(low<high) //判断长度大1 { pivotloc=Partition(L,low,high); //将l.r[low..high]一分为二 QSort(L,low,pivotloc-1); //对低子表递归排序，pivotloc是枢轴位置 QSort(L,pivotloc+1,high);//对高子表递归排序 } } int Partition(SqList2 &L,int low,int high) { int pivotkey; pivotkey=L.elemword[low]; //用子表的第一个记录作枢轴记录，枢轴记录关键字 while(low<high) //从表两端交替交替扫描 { while(low<high&&L.elemword[high]>=pivotkey) --high; L.elemword[low]=L.elemword[high];//比枢轴量记录晓移到低端 while(low<high&&L.elemword[low]<=pivotkey)// ++low; L.elemword[high]=L.elemword[low]; //比枢轴量记录大移到高地端 } L.elemword[low]=pivotkey; return low; } void PrintSqList(SqList2 L) { int i; printf("排列序列如下：\n"); for(i=1;i<=L.count;i++) printf("%4d",L.elemword[i]); printf("\n"); } //=============================================简单选择 typedef struct { int elemword[MAXSIZE]; int count; //记录数 }SqList3; void InitialSqList(SqList3&); void SelectSort(SqList3 &); int SelectMinKey(SqList3,int); void PrintSqList(SqList3); void InitialSqList(SqList3 &L) {//表初始化 int i; printf("请输入待排序的记录的个数:"); scanf("%d",&L.count); printf("请输入待排序的记录的关键字(整型数):\n"); for(i=1;i<=L.count;i++) scanf("%d",&L.elemword[i]); } void SelectSort(SqList3 &L) { int i,j,t; for(i=1;i<L.count;++i)//选择第i小的记录，并交换到位 { j=SelectMinKey(L,i); if(i!=j) //与第i个记录交换 { t=L.elemword[i]; L.elemword[i]=L.elemword[j]; L.elemword[j]=t; } } } int SelectMinKey(SqList3 L,int low)//选择key最小的记录 { int i,j,t; t=L.elemword[low]; j=low; for(i=low+1;i<=L.count;i++) if(L.elemword[i]<t) { t=L.elemword[i]; j=i; } return j; } void PrintSqList(SqList3 L) {//显示表中所有元素 int i; printf("排列序列如下：\n"); for(i=1;i<=L.count;i++) printf("%4d",L.elemword[i]); printf("\n"); } //=================================堆排序 typedef struct { int elemword[MAXSIZE]; int length; }SqList4; void InitialSqList(SqList4&); void HeapSort(SqList4 &); void HeapAdjust(SqList4 &,int,int); void PrintSqList(SqList4); void InitialSqList(SqList4 &L) { int i; printf("请输入待排序的记录的个数:"); scanf("%d",&L.length); printf("请输入待排序的记录的关键字(整型数):\n"); for(i=1;i<=L.length;i++) scanf("%d",&L.elemword[i]); } void HeapSort(SqList4 &L)//对顺序表H进行堆排序 { int i,t; for(i=L.length/2;i>0;--i) //把H.r[l..H.length]建成大顶堆,/2表示 HeapAdjust(L,i,L.length); for(i=L.length;i>1;--i) { t=L.elemword[1]; L.elemword[1]=L.elemword[i]; L.elemword[i]=t; HeapAdjust(L,1,i-1); //将H.r[1..i-1]重新调整为大顶堆 } } void HeapAdjust(SqList4 &H,int s,int m)// { int j,rc; rc=H.elemword[s]; for(j=2*s;j<=m;j*=2) { if(j<m&&H.elemword[j]<H.elemword[j+1]) ++j; //LT if(rc>=H.elemword[j]) break;//rc应插入在位置S上 H.elemword[s]=H.elemword[j]; s=j; } H.elemword[s]=rc;//插入 } void PrintSqList(SqList4 L) { int i; printf("已排好序的序列如下：\n"); for(i=1;i<=L.length;i++) printf("%4d",L.elemword[i]); printf("\n"); } //=======================================归并排序 typedef struct{ int key; }Elem; typedef struct { Elem elemword[MAXSIZE]; int length; }SqList5; void PrintSqList(SqList5 L) { int i; printf("排列序列如下：\n"); for(i=1;i<=L.length;i++) printf("%4d",L.elemword[i]); printf("\n\n"); } void MergingSort1(Elem sr[],Elem tr[],int i,int m,int n) { //将有序的SR[i,…,m]和SR[m+1,…,n]归并到有序的TR[i,…,n] int j,k,h; for(j=m+1,k=i;i<=m&&j<=n;k++) { if(sr[i].key<=sr[j].key) tr[k]=sr[i++]; //在程序中实现i,j的变化 else tr[k]=sr[j++]; } if(i<=m) { for(h=0;h<=m-i;h++) tr[k+h]=sr[i+h];}//将剩余的SR[i,…,m]复制到TR if(j<=n) { for(h=0;h<=n-j;h++) tr[k+h]=sr[j+h];}//将剩余的SR[m+1,…，n]复制到TR } void MergingSort(Elem sr[],Elem tr1[],int s,int t) { //将SR[s,…,t]归并到TR1[s,…,t] int m; Elem tr2[MAXSIZE+1]; if(s==t) tr1[s]=sr[s]; else { m=(s+t)/2; //将SR[s,…,t]平分为SR[s,,m]和SR[m+1,,t] MergingSort(sr,tr2,s,m); //递归地将SR[s,…,m]归并为有序的TR2[s,…,m] MergingSort(sr,tr2,m+1,t); //递归地将SR[m+1,…,t]归并为有序的TR2[m+1,…,n] MergingSort1(tr2,tr1,s,m,t); //将TR2[s,…,m]和TR2[m+1,…,t]归并到有序的TR1[s,…,t] } } void main() { while(1) { system("cls"); int c; printf("\n*****************************欢迎使用本程序*********************************"); printf("\n 1 折半插入排序\n"); printf(" 2 冒泡排序\n"); printf("\n 3 快速排序\n"); printf(" 4 简单选择排序\n"); printf("\n 5 归并排序\n"); printf(" 6 堆排序\n"); printf(" 7 退出本程序\n\n"); printf("*****************************欢迎使用本程序*********************************\n"); printf("请输入："); scanf("%d",&c); switch(c) { case 1: { system("cls"); SqList T; int key,i=1; printf("请输入数:\n"); scanf("%d",&key); getch(); while(key!=0) { T.r[i++].key=key; printf("请输入数:\n"); scanf("%d",&key); T.length=i-1; } BInsertSort(T); printf("查找结果：\n"); for(i=1;i<=T.length;i++) { printf("%d ",T.r[i].key); }