快速排序(算法与数据结构课程设计)

wilyes11收集博客(与学习无关)：快速排序一、问题描述排序是数据结构中典型的算法，经常有插入排序、选择排序、快速排序等。本文要求对排序表中的无序数据进行快速排序，并讨论快速排序的改进方法（双倍快速排序、基于归并的快速排序），这样可以对排序进行优化，提高效率。二、基本要求1、选择合适的存储结构建立排序表，并能遍历表输出元素。2、编写快速排序算法，并能够输出排序的结果。3.快速排序及其改进—双倍快速排序和基于归并的快速排序算法。三、测试数据输入以下数据：5、3、7、11、1、9、4、8四、算法思想1、普通快速排序的基本思想：可以运用一趟快速排序把序列分成分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行快速排序，以达到整个序列有序。一趟的快速排序是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey,则首先从high所指位置起向前搜索到第一个关键字小于pivotkey大的记录和枢轴记录互相交换，然后从low所指位置向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两部直至low=high为止。2、双倍快速排序思想：快速排序的基本思想是基于分支策略的思想。即对于输入的子序列L[low..high],如果规模足够小则直接进行排序,否则分三步处理:1)分解(Divide):设输入的序列L[low..High],确定支点元素L[low]和L[High],并使L[Low].key=Ll[High].key,然后分解(Divide):将序列L[low..High]划分成三个子序列L[Low..L-1]、L[L+1..H-1]和L[H+1..High],使L[low..High]中元素的关系为L[Low..L-1]L[L]L[L+1..H-1]L[H]L[H+1..High]。2)递归求解(Conquer):通过递归调用快速排序算法分别对L[Low..L-1]、L[L+1..H-1]和L[H+1..High]分别进行分解排序。3)合并(Merge):对分解出的三个子序列的排序是就地进行的,所以在L[Low..L-1]、L[L+1..H-1]和L[H+1..High]都排好序后不需要执行任何计算L[low..High]就已排好序。3、基于归并的快速排序：对划分结果产生的两个子序列的长度进行检查，如果其中一个与另一个的长度比超过某一界限，则认为这是一个“畸形划分”，对较短的子序列继续使用“快速排序”，而把较长的子序列平分为两个子序列分别排序，然后再进行一次合并。两个有序序列的合并是可以实现为线性的时间复杂度的，因此可以在每次都是畸形划分时仍然wilyes11收集博客(与学习无关)：获得)*(LogNNO的时间复杂度。其中Partition就是众所周知的用于“快速排序”的划分子程序，Merge(Data,First,Size)把Data中[0,First)和[First,Size)两个有序列合并为一个有序序列并存放在Data中。Partition划分的位置M处的值就是划分的枢值，也就是说序列可以分成[0,M-1]、[M,M]和[M+1,Size-1]三部分。如果Partition的实现不能保证这一点，则MoreData应为Data[M]，而MoreSize也应为Size-M。五、模块划分1、voidCreate(SqList*L)，建立排序表。2、voidTraverse(SqListL)，遍历排序表(输出哨兵)。3、voidswap(int*a,int*b)，用于交换两个数。4、intPartition(SqList*L,intlow,inthigh)，将一个序列划分成两个子序列，后一子序列所有值都不大于前一子序列任意值。返回子序列分割处索引。5、voidQSort1(SqList*L,intlow,inthigh)，调用快排函数进行排序。6、intQSort2(SqList*L,intlow,inthigh)，调用双倍快排函数进行排序。7、voidMerge(RedTypeSR[],RedTypeTR[],inti,intm,intn)，两个有序序列合并为一个有序列序。8、voidMSort(RedTypeSR[],RedTypeTR1[],ints,intt)，归并排序。9、intqsort1(SqList*L,intlow,inthigh)，快速排序。10、voidmenu，输出时清晰。11、intmain()，主函数。六、数据结构//(ADT)数据类型typedefintKeyType;/*定义关键字类型为整数类型*/typedefstruct{KeyTypekey;/*定义关键字*//*其它域:略*/}RedType;/*记录类型*/typedefstruct{RedTyper[MAXSIZE+1];/*定义数组*/intlength;/*表长*/}SqList;/*顺序表类型*/七、源程序#includestdio.hwilyes11收集博客(与学习无关)：(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineLQ(a,b)((a)=(b))typedefintKeyType;typedefstruct{KeyTypekey;/*其它域:略*/}RedType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;/*排序表的建立*/voidCreate(SqList*L){inti,n;printf(\n请输入表长:);scanf(%d,&n);printf(请输入%d元素:,n);for(i=1;i=n;i++)scanf(%d,&(L-r[i].key));L-length=n;}/*遍历排序表(输出哨兵)*/voidTraverse(SqListL){inti;for(i=1;i=L.length;i++)printf(%6d,L.r[i].key);}/*交换函数*/voidswap(int*a,int*b)wilyes11收集博客(与学习无关)：{inttemp;temp=*a;*a=*b;*b=temp;}/*快速排序*/intPartition(SqList*L,intlow,inthigh){KeyTypepivotkey;/*关键字*/L-r[0]=L-r[low];pivotkey=L-r[low].key;while(lowhigh){while(lowhigh&&L-r[high].key=pivotkey)high--;L-r[low]=L-r[high];while(lowhigh&&L-r[low].key=pivotkey)low++;L-r[high]=L-r[low];}L-r[low]=L-r[0];Traverse(*L);/*每一趟的输出*/printf(\n);returnlow;}/*快速排序函数*/voidQSort1(SqList*L,intlow,inthigh){intpivotloc;/*设置枢轴*/if(lowhigh){pivotloc=Partition(L,low,high);QSort1(L,low,pivotloc-1);QSort1(L,pivotloc+1,high);}}/*双倍快速排序函数*/intQSort2(SqList*L,intlow,inthigh){intn,Ls,Hs,i;/*设置两个枢轴从两头一起排序*/n=high-low;/*控制循环次数*/if(lowhigh||low==high)return1;if(L-r[low].keyL-r[high].key)wilyes11收集博客(与学习无关)：*确保区间内第一个元素的值不大于区间内最后一个元素的值*/swap(&L-r[low].key,&L-r[high].key);Ls=low;Hs=high;for(i=low+1;i=n;i++){if(L-r[i].keyL-r[low].key)//小于区间第一个元素的值放置第一区间内{Ls++;swap(&L-r[i].key,&L-r[Ls].key);/*交换两数*/}elseif(L-r[i].keyL-r[high].key){Hs--;swap(&L-r[i].key,&L-r[Hs].key);/*交换两数*/i--;/*下一个比较位置不变*/n--;/*循环次数减1*/}}swap(&L-r[Ls].key,&L-r[low].key);/*交换两数*/swap(&L-r[Hs].key,&L-r[high].key);/*交换两数*/Traverse(*L);/*每一趟的输出*/printf(\n);QSort2(L,low,Ls-1);/*对分解后的第一部分递归快速排序*/QSort2(L,Ls+1,Hs-1);/*对分解后的第二部分第归快速排序*/QSort2(L,Hs+1,high);/*对分解后的第三部分第归快速排序*/return0;}/*基于归并的快速排序*/voidMerge(RedTypeSR[],RedTypeTR[],inti,intm,intn)/*调用归并函*/{intj,k;/*定义两数*/for(j=m+1,k=i;i=m&&j=n;++k){ifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i=m)wilyes11收集博客(与学习无关)：(k=n&&i=m)TR[k++]=SR[i++];if(j=n)while(k=n&&j=n)TR[k++]=SR[j++];}voidMSort(RedTypeSR[],RedTypeTR1[],ints,intt)/*调用归并函数*/{intm;RedTypeTR2[20];if(s==t)TR1[t]=SR[s];else{m=(s+t)/2;MSort(SR,TR2,s,m);/*调用归并函数*/MSort(SR,TR2,m+1,t);/*调用归并函数*/Merge(TR2,TR1,s,m,t);/*主要消除畸形划分*/}}intqsort1(SqList*L,intlow,inthigh)/*返回整数类型的快排*/{intk,f,s,r,mid;r=N-1;if(lowhigh)return1;k=Partition(L,low,high);f=k-low;s=high-k;if(fs&&s!=0)r=f/s;/*检查其中一个子序列与另一个的长度比是否超过某一界限*/elseif(f!=0)r=s/f;if(rM){mid=(k-1-low)/2+s;/*较长的子序列平分为两个子序列*/QSort1(L,s,mid);/*此时进行快速排序*/QSort1(L,mid+1,k-1);MSort(L-r,L-r,mid,k-1);mid=(f-k-1)/2+k+1;QSort1(L,k+1,mid);QSort1(L,mid+1,f);wilyes11收集博客(与学习无关)：