文件名称:
各种排序 冒泡 快速 堆 希尔 基数等九种
开发工具:
文件大小: 256kb
下载次数: 0
上传时间: 2010-05-28
详细说明： #include #include #define MAXSIZE 10 #define MAX_BIT 8 // 关键字最大位数 #define RADIX 10 // 关键字基数 ，此时是十进制整数的基数 #define MAX_SPACE 8 // 分配的存储空间的大小 typedef char KeyType;// define the keyType is the int typedef int InfoType; typedef struct { KeyType key; InfoType otherinfo;// 其他数据项 }RedType; typedef struct { RedType r[MAXSIZE+1];// r[0] is for the guard int length; }SqList; // Radix Sorting struct SLNode { KeyType key[MAX_BIT]; // the key InfoType otheritems; // 其他数据项 int next; // 下一个节点的下标位置 }; // 静态链表中的节点类型 struct SList { struct SLNode r[MAX_SPACE]; // 静态链表中各节点，其中r[0]为头结点 int keybit; // 关键字的位数 int recnum; // 静态链表中记录的个数 }; // 静态链表的类型 // 函数声明 void Insert_Sort ( SqList &L);// the Straight Insertion Sort void BInsert_Sort(SqList &L);// the Binary Insertion Sort void Shell_Sort(SqList &L);// Shell Sort int Partition ( SqList &L,int low,int high ); void Quick_Sort(SqList &L,int low,int high);// Quick Sort void Bubble_Sort(SqList &L); void Select_Sort( SqList &L); void Heap_Sort(SqList &L); void Merge_Sort(SqList &L);// Merging Sort void display(SqList L);// 输出显示 void main() { SqList L; L.length=MAXSIZE; int i,msg; char ch; do { system("cls"); // 清屏 cout<<"please input the data:"<>L.r[i].key; } cout<<"1、直接插入排序"<<"\t"; cout<<"2、折半插入排序"<>msg; switch (msg) { case 1: Insert_Sort(L); display(L); break; case 2: BInsert_Sort(L); display(L); break; case 3: Shell_Sort(L); display(L); break; case 4: Bubble_Sort(L); display(L); break; case 5: Quick_Sort(L,1,L.length); display(L); break; case 6: Select_Sort(L); display(L); break; case 7: Heap_Sort(L); display(L); break; case 8: Merge_Sort(L); display(L); break; default: cout<<"please input 1至 8"<>msg; } cout<<"do you want to continue !(y or n):"; cin>>ch; } while(ch=='Y'||ch=='y'); } // 直接插入排序 void Insert_Sort(SqList &L) { int i,j; for (i=2; i<=L.length; i++) { if (L.r[i].key=high+1; --j) { L.r[j+1]=L.r[j]; } L.r[high+1] = L.r[0]; // insert it } } // 希尔排序 void Shell_Sort(SqList &L)// the ascending order { int d = L.length,i; while ( d>=1 ) { d=d/2; for (i = 1+d; i<=L.length; i++) if (L.r[i].key < L.r[i-d].key) { L.r[0]=L.r[i]; for (int j=i-d; j>0&&L.r[0].key =pivotkey) { high--; } L.r[low]=L.r[high];// while(False) while (lowL.r[j+1].key) { L.r[0]=L.r[j+1]; L.r[j+1]=L.r[j]; L.r[j]=L.r[0]; flag=1; } } i++; } } void Select_Sort( SqList &L)// 直接选择排序 { int i,j,min; for (i=1; i<= L.length; i++) { min=i; for (j=i+1; j<=L.length; j++) { if (L.r[min].key>L.r[j].key) { min=j; } } if (min!=i) { L.r[0]=L.r[i]; L.r[i]=L.r[min]; L.r[min]=L.r[0]; } } } void Heap_Adjust(SqList &L,int s, int m)// 堆调整 { // 在L.r[s...m]中记录的关键字除L.r[s].key 之外均满足堆的定义，本函数调整L.r[s]的关键字，使L.r[s...m]成为一个大顶堆 int j; L.r[0]=L.r[s]; for ( j=2*s; j<=m; j*=2 ) { // 沿key较大的孩子节点向下筛选 if (j=L.r[j].key) { break; } else// 将三者中的最大值放入到根节点的位置，并用s记录此位置 { L.r[s]=L.r[j]; s=j; } } L.r[s]=L.r[0]; } void Heap_Sort(SqList &L) // 堆排序 { int i; for (i=L.length/2; i>0; i--)// build the heap { Heap_Adjust(L,i,L.length); } for (i=L.length; i>1; i--) { L.r[0]=L.r[i];// 将 堆顶记录和当前未经排序子队列（1——i）中 的 最后一个记录 交换 L.r[i]=L.r[1]; L.r[1]=L.r[0]; Heap_Adjust(L,1,i-1);// 将（1——i-1）重新调整为一个大堆 } } void Merge( RedType S[], RedType T[], int i,int m,int n) { // 将有序的S前一部分和后一部分归并为有序的T int j,k; for (j=m+1,k=i;i<=m && j<=n; ++k)// 将S中记录由小到大并入到T中 { if (S[i].key<=S[j].key) { T[k]=S[i++]; } else T[k] = S[j++]; } while(i<=m)// 将剩余的S[i...m]复制到T中 T[k++]=S[i++]; while(j<=n)// 将剩余的S[j...n]复制到T T[k++]=S[j++]; } void MSort(RedType S[],RedType T1[],int s,int t ) { // 将S[s...t]归并为T[s...t]MAXSIZE+1 RedType T2[MAXSIZE+1]; int m; if ( s==t )// 只有一个记录 { T1[s] = S[s]; } else { m=(s+t)/2; // 将S 分为2份 MSort(S,T2,s,m);// 将S归并为有序的T2 MSort(S,T2,m+1,t); // 将S归并为有序的T2 Merge(T2, T1,s,m,t); // 将T1和T2归并到T1中 } } void Merge_Sort(SqList &L)// 归并排序 { // 对顺序表L作归并排序 MSort(L.r,L.r,1,L.length); } // for Radix Sorting // 基数排序中一趟分配的算法 void Distribute (SLNode *r,int i,int f[RADIX],int e[RADIX]) { // 静态链表中的r域中记录已按key[0]——key[i-1]有序 // 本算法按关键字的第i位建立RADIX个链队列，使在同一链队列中关键字的第i位的数值相等； // f、e均为长度为RADIX的指针数组,分别指向各链队列的第一条和最后一条记录 int j,p; for (j=0; j
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
