八大排序算法(4)

然后再把有序子序列合并为整体有序序列。归并排序示例： 合并方法：设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。

j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束//选取r[i]和r[j]较小的存入辅助数组rf 如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵

否则，rf[k]=r[j]； j++； k++； 转⑵//将尚未处理完的子表中元素存入rf

如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空 如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空合并结束。//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] void Merge(ElemType *r,ElemType *rf, int i, int m, int n) { int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; } 归并的迭代算法

1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有

序的表。void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<\ \ } cout<<endl; } //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] void Merge(ElemType *r,ElemType *rf, int i, int m, int n) { int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; print(rf,n+1); } void MergeSort(ElemType *r, ElemType *rf, int lenght) { int len = 1; ElemType *q = r ; ElemType *tmp ; while(len

< lenght) { int s = len; len = 2 * s ; int i = 0; while(i+ len

<lenght){ Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表合并 i = i+ len; } if(i + s <

lenght){ Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并 } tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf } } int main(){ int a[10] = {3,1,5,7,2,4,9,6,10,8}; int b[10]; MergeSort(a, b, 10); print(b,10); cout<<\结果：\

print(a,10); } 两路归并的递归算法void MSort(ElemType *r, ElemType *rf,int s, int t) { ElemType *rf2; if(s==t) r[s] = rf[s]; else { int m=(s+t)/2; /*平分*p 表*/ MSort(r, rf2, s, m); /*递归地将p[s…m]归并为有序的p2[s…m]*/ MSort(r, rf2, m+1, t); /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/ Merge(rf2, rf, s, m+1,t); /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/ } } void MergeSort_recursive(ElemType *r, ElemType *rf, int n) { /*对顺序表*p 作归并排序*/ MSort(r, rf,0, n-1); } 8. 桶排序/基数排序(Radix Sort)说基数排序之前，我们先说桶排序：基本思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。

例如要对大小为[1..1000]范围内的n个整数A[1..n]排序 首先，可以把桶设为大小为10的范围，具体而言，设集合

B[1]存储[1..10]的整数，集合B[2]存储 (10..20]的整数，……集合B[i]存储( (i-1)*10, i*10]的整数，i = 1,2,..100。总共有 100个桶。 然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任 何排序法都可以。 最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这 样就得到所有数字排好序的一个序列了。 假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果 对每个桶中的数字采用快速排序，那么整个算法的复杂度是 O(n + m *

n/m*log(n/m)) = O(n + nlogn - nlogm) 从上式看出，当m接近n的时候，桶排序复杂度接近O(n) 当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。 前面说的几大排序算法 ，大部分时间复杂度都是O（n2），也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O（n）的时间复杂度。但桶排序的缺点是： 1）首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到

m-1，那就需要m个桶，这个桶数组就要至少m个空间。 2）其次待排序的元素都要在一定的范围内等等。 桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较，但前提是要知道待排序列的一些具体情况。 分配排序的基本思想：说白了就是进行多次的桶式排序。基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。 实例:扑克牌中52 张牌，可按花色和面值分成两个字段，其大小关系为：

花色： 梅花< 方块< 红心< 黑心

面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A若对扑克牌按花色、面值进行升序排序，得到如下序列：即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这就是多关键码排序。为得到排序结果，我们讨论两种排序方法。

方法1：先对花色排序，将其分为4 个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4 个组连接起来即可。

方法2：先按13 个面值给出13 个编号组(2 号，3 号，...，A 号)，将牌按面值依次放入对应的编号组，分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心)，将2号

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库八大排序算法(4)在线全文阅读。