C++两路归并算法
归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。
两路归并算法
1、算法基本思路
设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。
（1）合并过程
合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。
重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。
（2）动态申请R1
实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。
2、归并算法
void Merge(SeqList R，int low，int m，int high)
{//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的
//子文件R[low..high]
int i=low，j=m+1，p=0；//置初始值
RecType *R1；//R1是局部向量，若p定义为此类型指针速度更快
R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))；
if(! R1) //申请空间失败
Error("Insufficient memory available!")；
while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；
while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中
R1[p++]=R[i++]；
while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中
R1[p++]=R[j++]；
for(p=0，i=low；i<=high；p++，i++)
R[i]=R1[p]；//归并完成后将结果复制回R[low..high]
} //Merge
归并排序
归并排序有两种实现方法：自底向上和自顶向下。
1、自底向上的方法
（1）自底向上的基本思想
自底向上的基本思想是：第1趟归并排序时，将待排序的文件R[1..n]看作是n个长度为1的有序子文件，将这些子文件两两归并，若n为偶数，则得到个长度为2的有序子文件；若n为奇数，则最后一个子文件轮空(不
参与归并)。故本趟归并完成后，前个有序子文件长度为2，但最
后一个子文件长度仍为1；第2趟归并则是将第1趟归并所得到的个有
序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止。
上述的每次归并操作，均是将两个有序的子文件合并成一个有序的子文件，故称其为"二路归并排序"。类似地有k(k>2)路归并排序。
（2）二路归并排序的全过程
【参见动画演示】
（3）一趟归并算法
分析：
在某趟归并中，设各子文件长度为length(最后一个子文件的长度可能小于length)，则归并前R[1..n]中共有个有序的子文件：R
[1..length]，R[length+1..2length]，…，。
注意：
调用归并操作将相邻的一对子文件进行归并时，必须对子文件的个数可能是奇数、以及最后一个子文件的长度小于length这两种特殊情况进行特殊处理：
①若子文件个数为奇数，则最后一个子文件无须和其它子文件归并(即本趟轮空)；
②若子文件个数为偶数，则要注意最后一对子文件中后一子文件的区间上界是n。
具体算法如下：
void MergePass(SeqList R，int length)
{ //对R[1..n]做一趟归并排序
int i；
for(i=1;i+2*length-1<=n;i=i+2*length)
Merge(R，i，i+length-1，i+2*length-1)；
//归并长度为length的两个相邻子文件
if(i+length-1 Merge(R，i，i+length-1，n)；//归并最后两个子文件 //注意：若i≤n且i+length-1≥n时，则剩余一个子文件轮空，无须归并 } //MergePass （4）二路归并排序算法 void MergeSort(SeqList R) {//采用自底向上的方法，对R[1..n]进行二路归并排序 int length； for(1ength=1；length MergePass(R，length)；//有序段长度≥n时终止 } 注意： 自底向上的归并排序算法虽然效率较高，但可读性较差。 2、自顶向下的方法 采用分治法进行自顶向下的算法设计，形式更为简洁。 （1）分治法的三个步骤 设归并排序的当前区间是R[low..high]，分治法的三个步骤是： ①分解：将当前区间一分为二，即求分裂点 ②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序； ③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。 递归的终结条件：子区间长度为1（一个记录自然有序）。 （2）具体算法 void MergeSortDC(SeqList R，int low，int high) {//用分治法对R[low..high]进行二路归并排序 int mid； if(low mid=(low+high)/2；//分解 MergeSortDC(R，low，mid); //递归地对R[low..mid]排序 MergeSortDC(R，mid+1，high)；//递归地对R[mid+1..high]排序 Merge(R，low，mid，high)；//组合，将两个有序区归并为一个有序区 } }//MergeSortDC （3）算法MergeSortDC的执行过程 算法MergeSortDC的执行过程如下图所示的递归树。 二、算法分析 1、稳定性 归并排序是一种稳定的排序。 2、存储结构要求 可用顺序存储结构。也易于在链表上实现。 3、时间复杂度 对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。 4、空间复杂度 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。 注意： 若用单链表做存储结构，很容易给出就地的归并排序。具体【参见练习】。 #include count++; }//满足条件，前移 if(count==0) break;//位置恰当，退出 } } }//insort插入排序函数 selsort(int a[30001]) { int i,j,temp; for(i=1;i<30000;i++) for(j=i+1;j<30001;j++) if(a[i]>a[j]) { temp=a[j]; a[j]=a[i]; a[i]=temp; } }//选择排序 bubsort(int a[30001]) { int i,j,temp; for(i=1;i<30001;i++) for(j=30000;j>i;j--) { if(a[j-1]>a[j]) { temp=a[j-1]; a[j-1]=a[j]; a[j]=temp; } } }//冒泡排序 int partition(int a[30001],int low,int high) import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Random; public class GuiBing { public static void main(String[] args) throws Exception { int datalength=1000000; GuiBing gui=new GuiBing(); int[] array1=gui.createArray(datalength); int[] array2=gui.createArray(datalength); Thread.sleep(20000); long startTime = System.nanoTime();//纳秒精度 long begin_freeMemory=Runtime.getRuntime().freeMemory(); int[] final_array=gui.guibing(array1,array2); boolean result=gui.testResult(final_array); long end_freeMemory=Runtime.getRuntime().freeMemory(); System.out.println("result===="+result); long estimatedTime = System.nanoTime() - startTime; System.out.println("elapsed time(纳秒精 度):"+estimatedTime/100000000.0); System.out.println("allocated memory:"+(begin_freeMemory-end_freeMemory)/1000.0+" KB"); Thread.sleep(20000); } /** * 显示数组的内容 * @param array */ private static void dispalyData(int[] array) { for(int i=0;i 归并排序算法实现（迭代和递归）\递归实现归并排序的原理如下： 递归分割: 递归到达底部后排序返回: 最终实现排序： #include } while(i 实验名称归并排序分治策略的设计与实现实验方案实验成绩实验日期实验室信息系统设计与仿真室I 实验操作 实验台号班级姓名实验结果 一、实验目的 1、熟悉分治法求解问题的抽象控制策略； 2、熟悉在顺序存储表示下求解分类问题的递归算法设计； 3、通过实例转换, 掌握分治法应用。 二、实验任务 ①从文件中读取数据信息； ②利用归并排序算法，进行排序； ③输出排序结果。 三、实验设计方案 1、结构体设计 用数组存放排序数据。 2、自定义函数设计 ①函数原型声明 int input(int A[]); //从文件读入待排序的数据 void merge(int A[],int low,int mid,int high); // 两个相邻有序数组的归并 void mergesort(int A[],int low,int high); // 归并排序 void input(int A[], int n); // 输出排序结果 ②两个相邻的有序子数组的合并 思路：从两个已排好序的子数组的首元素开始，依次比较大小，按从小到大的顺序存放在b[]数组中，然后转存到A[]数组中。 void merge(int A[],int low,int mid,int high) { int b[N]; int i,j,k = 0; int l = low; //已排序部分1的起始下标 int h = mid+1; //已排序部分2的起始下标 while(l <= mid && h <= high) //两个有序部分合并到b数组中 if(A[l] < A[h]) b[k++] = A[l++]; else 算法分析与设计实验报告第二次实验 对于归并排序，在之前的数据结构已经学过了，本来以为代码实现起来会比较 附录： 完整代码（分治法） #include { for(int last=i;last<=mid;last++) { B[k++]=A[last]; } } } void mergesort(int a[],int b[],int left,int right) //分治法实现归并排序，利用递归实现{ if(left 1 排序 排序是数据处理中经常使用的一种重要运算，如何进行排序，特别是如何进行高效的排序，是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件，而记录则是由若干数据项组成，其中的一项可用来标志一个记录，称为关键字项，该数据项的值称为关键字。所谓排序，就是要整理文件中的记录，使得它按关键字递增（或递减）的次序排列起来。若给定的文件含有n个记录｛R1，R2，…，R n｝，它们的关键字分别为｛K1，K2，…，K n｝，要把这n个记录重新排列成为｛R i1，R i2，…，R in｝，使得｛K i1≥K i2≥…≥K in｝（或｛K i1≤K i2≤…≤K in｝）。 本章主要介绍了枚举排序、快速排序、PSRS排序算法以及它们的MPI编程实现。1.1 枚举排序 1.1.1 枚举排序及其串行算法 枚举排序（Enumeration Sort）是一种最简单的排序算法，通常也称为秩排序（Rank Sort）。该算法的具体思想是（假设按关键字递增排序），对每一个待排序的元素统计小于它的所有元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a[1]…a[n]中。首先将a[1]与a[2]…a[n]比较，记录比其小的数的个数，令其为k，a[1]就被存入有序的数组b[1]…b[n]的b[k+1]位置上；然后将a[2]与a[1]，a[3]…a[n]比较，记录比其小的数的个数，依此类推。这样的比较操作共n(n-1)次，所以串行秩排序的时间复杂度为O（n2）。 算法13.1 枚举排序串行算法 输入：a[1]…a[n] 输出：b[1]…b[n] Begin for i=1 to n do (1) k=1 (2) for j=1 to n do if a[i]>a[j] then k=k+1 end if end for (3) b[k]= a[i] end for End 1.1.2 枚举排序的并行算法 对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需是每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。该并行算法描述如下： 算法13.2 枚举排序并行算法 关于多路归并排序外部排序败者树技术积累2009-11-24 21:52:06 阅读453 评论0 字号：大中小 编程珠玑第一个case是有关一个技巧性解决外部排序问题的。问题很巧妙的解决了，但一开始提到的利用归并排序进行外部排序的算法仍值得仔细探究一下，毕竟本科时学的不是很深入。 先来看内部排序中最简单的2路归并排序算法。 算法核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，给定数组中序列界限i、m、n，用2个下标变量分别从i和j=m+1开始逐个往后处理，先比较，小的写到结果序列的当前遍历下标k中，相应下标自增继续比较直到某个序列的下标走到边界，再将另外一个序列的剩余元素拷贝到结果序列中。 算法可用递归或递推实现，从相邻的两两元素开始不断调用上面的核心操作组成较长有序序列直到完成整个序列。 算法进行一趟归并就得到一个局部有序的完整新序列，n个元素共需要log2n趟归并，每趟完成比较操作n次（1次得到序列的1个值），得到的新序列写到结果序列空间中，下一趟之前要先将结果序列复制一份到临时空间，下一趟归并在临时空间上进行。因此时间复杂度nlog2n，空间上除了原始序列空间n、结果序列空间n，还需要辅助临时空间n。 接下来看外部排序。外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序。 多路归并排序算法在常见数据结构书中都有涉及。从2路到多路（k路），增大k可以减少外存信息读写时间，但k个归并段中选取最小的记录需要比较k-1次，为得到u个记录的一个有序段共需要(u-1)(k-1)次，若归并趟数为s次，那么对n个记录的文件进行外排时，内部归并过程中进行的总的比较次数为s(n-1)(k-1)，也即(向上取整)(logkm)(k-1)(n-1)=(向上取整)(log2m/log2k)(k-1)(n-1)，而(k-1)/log2k随k增而增因此内部归并时间随k增长而增长了，抵消了外存读写减少的时间，这样做不行，由此引出了“败者树”tree of loser的使用。在内部归并过程中利用败者树将k个归并段中选取最小记录比较的次数降为(向上取整)(log2k)次使总比较次数为(向上取整)(log2m)(n-1)，与k无关。 败者树是完全二叉树，因此数据结构可以采用一维数组。其元素个数为k个叶子结点、k-1个比较结点、1个冠军结点共2k个。ls[0]为冠军结点，ls[1]--ls[k-1]为比较结点，ls[k]--ls[2k-1]为叶子结点（同时用另外一个指针索引b[0]--b[k-1]指向）。另外bk为一个附加的辅助空间，不属于败者树，初始化时存着MINKEY的值。 多路归并排序算法的过程大致为：首先将k个归并段中的首元素关键字依次存入 篇一：归并排序与快速排序实验报告 一、实验内容： 对二路归并排序和快速排序对于逆序的顺序数的排序时间复杂度比较。 二、所用算法的基本思想及复杂度分析： 1、归并排序 1）基本思想：运用分治法，其分治策略为： ①划分：将待排序列 r1,r2,……,rn划分为两个长度相等的子序列 r1,……,rn/2和rn/2+1,……,rn。 ②求解子问题：分别对这两个子序列进行排序，得到两个有序子序列。 ③合并：将这两个有序子序列合并成一个有序子序列。 2）复杂度分析： 二路归并排序的时间代价是o(nlog2n)。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性o(n)。 2、快速排序： 1）基本思想：运用分治法，其分治策略为： ①划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列 r1……ri-1和ri+1……rn，轴值的位置i在划分的过程中确定，并且前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值。 ②求解子问题：分别对划分后的每一个子序列递归处理。 ③合并：由于对子序列r1……ri-1和ri+1……rn的排序是就地进行的，所以合并不需要执行任何操作。 2）复杂度分析： 快速排序在平均时间复杂性是o(nlog2n)。最坏的情况下是o(n^2)。 三、源程序及注释： 1、归并排序 #include<iostream> #include<fstream> #include windows.h using namespace std; void merge(int r[],int r1[],int s,int m,int t ) } int mergesort(int r[],int r1[],int s,int t) { } void main() int i=s; int j=m+1; int k=s; while(i<=m&&j<=t) {} if(i<=m)while(i<=m) r1[k++]=r[i++];//第一个没处理完，进行收尾if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中较小的放入r1[k]中else r1[k++]=r[j++]; else while(j<=t) r1[k++]=r[j++];//第二个没处理完，进行收尾for(int l=0;l<k;l++) { } r[l]=r1[l];//将合并完成后的r1[]序列送回r[]中if(s==t)r1[s]=r[s]; else{int m; m=(s+t)/2; mergesort(r,r1,s,m);//归并排序前半个子序列 mergesort(r,r1,m+1,t); //归并排序后半个子序列 merge(r1,r,s,m,t);//合并两个已排序的子序列 }return 0; int a[100000]; int a1[10000]; 归并排序算法的基本思想及算法实现示例 归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。 两路归并算法 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。 （1）合并过程 合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。 重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。 （2）动态申请R1 实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。 2、归并算法 void Merge(SeqList R，int low，int m，int high) {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 //子文件R[low..high] int i=low，j=m+1，p=0；//置初始值 RecType *R1；//R1是局部向量，若p定义为此类型指针速度更快 R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))； if(! R1) //申请空间失败 Error("Insufficient memory available!")； while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]； while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中 R1[p++]=R[i++]； while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中 R1[p++]=R[j++]； for(p=0，i=low；i<=high；p++，i++) R=R1[p]；//归并完成后将结果复制回R[low..high] } //Merge 归并排序 归并排序有两种实现方法：自底向上和自顶向下。 大连理工大学实验预习报告 学院（系）：电信专业：班级： 姓名：学号：组：___ 实验时间：实验室：实验台： 指导教师签字：成绩： 实验名称Merge sort 一、实验目的和要求 (一)、实验目的 Design the merge sort algorithm and implement it in C language 设计归并排序算法并于C语言实现。 (二)、实验要求 Requirements: 1) Analyze the time complexity of your algorithm 2) Submit the document explaining your algorithm as well as the source code. 要求： 1)分析算法的时间复杂度。 2) 提交的文档中说明你的算法和源代码。 二、实验原理 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可 解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？ 可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。 串行归并与并行归并排序算法 一、串行归并排序算法 归并排序是一种很容易进行并行化的算法，因为归并的各个数据区间都是独立的，没有依赖关系。并且归并排序是一种速度比较快的排序，且是一种稳定的排序算法，排序速度与关键词初始排列无关。 串行归并排序的算法大体的可以描述为：首先将要排序的表分成两个节点个数基本相等的子表，然后对每个子表进行排序，最后将排好序的两个子表合并成一个子表。在对子表进行排序时可以将子表再分解成两个节点数量基本相同的子表，当子表足够小时，也可以采用其他排序方法对子表进行排序，然后再对排好序的子表进行归并操作，最后将整个表排好序。 1、1算法流程图 并行归并排序算法的流程图： 串行归并排序算发流程图 1、2代码分析 #include package com.igo.util.file; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; import org.slf4j.Logger; /** * * 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存， * 需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。* 外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装人内存的部分， * 分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。* @author ZhaoWeikai * Company: * 2010-12-23 下午02:25:00 */ public class MergeSort { private static final Logger log = org.slf4j.LoggerFactory.getLogger(MergeSort.class); /** 拆分大小, 单位:行*/ private static int SPLIT_SIZE = 100000; public static void main(String[] args) throws Exception { List 算法与数据结构实验报告 实验六 实验名称:归并排序问题 姓名：XXX 学号：xxxxxxxxxx 专业：软件工程 班级：x班 指导教师：xxx 日期: 2013年X月X日 一、实验目的 了解归并排序的排序思想，对于给定的关键字序列进行归并排序输出。二、实验内容与实验步骤 内容：设计二路归并算法。 问题描述如下：输入数据第1行有1整数k，表示需要排序的序列个数。以下k行，每行第一个整数m，表示待排序序列的长度，后面的m个整数表示待排序序列。将k个待排序序列的归并排序结果分k行输出。 步骤： 1将一维数组中前后相邻的两个有序序列归并为一个有序序列； 其算法为：void merge(dataList& L, dataList& L1,int left, int mid, int right){}； 2 对顺序表L作归并排序； 其算法为：void MergePass (dataList& L, dataList& L1, int len){}； 3 将SR[s..t]归并为排序为TR1[s..t]； 其算法为：void MergeSort (dataList& L){}； 4 调试数据，程序结束； 三、实验环境 操作系统winXP、开发平台:Microsoft Visual C++6.0 四、实验过程与分析 归并排序算法大大缩短了排序的时间复杂度，虽然程序代码复杂，但实现的基理相当简单。从运行结果可知，该程序达到了预期效果。 五、实验结论 测试数据：测试结果： 3 7 49 38 65 97 76 13 27 13 27 38 49 65 76 97 10 36 25 48 12 65 25 43 58 76 32 12 25 25 32 36 43 48 58 65 76 6 12 32 49 58 65 79 12 32 49 58 65 79 运行结果： #include tabg->r[k+t-i]=tabs->r[t]; else for(t=j; t<=v; t++) tabg->r[k+t-j]=tabs->r[t]; } void mergepass(table *tabs,table *tabg,int len) { int i,j,n; n=tabg->length=tabs->length; i=1; while(i<=n-2*len+1) { merge(tabs,tabg,i,i+len-1,i+2*len-1); i=i+2*len; } if(i+len-1 数据结构实验报告 八种排序算法实验报告 一、实验内容 编写关于八种排序算法的C语言程序，要求包含直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。 二、实验步骤 各种内部排序算法的比较： 1.八种排序算法的复杂度分析（时间与空间）。 2.八种排序算法的C语言编程实现。 3.八种排序算法的比较，包括比较次数、移动次数。 三、稳定性，时间复杂度和空间复杂度分析 比较时间复杂度函数的情况： 时间复杂度函数O(n)的增长情况 所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。 时间复杂度来说： (1)平方阶(O(n2))排序 各类简单排序:直接插入、直接选择和冒泡排序； (2)线性对数阶(O(nlog2n))排序 快速排序、堆排序和归并排序； (3)O(n1+§))排序,§是介于0和1之间的常数。 希尔排序 (4)线性阶(O(n))排序 基数排序，此外还有桶、箱排序。 说明： 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）； 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）； 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。 稳定性： 排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。 稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较； 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序 答：（1）归并排序算法 #include 并行排序算法 先简单说一下给的A，B，C 三种算法(见上面引用的那篇博客)，A算法将耗时的平方和开平方计算放到比较函数中，导致Array.Sort 时，每次亮亮比较都要执行平方和开平方计算，其平均算法复杂度为 O(nlog2n) 。而B 将平方和开平方计算提取出来，算法复杂度降低到 O(n) ，这也就是为什么B比A效率要高很多的缘故。C 和 B 相比，将平方函数替换成了 x*x ，由于少了远程函数调用和Pow函数本身的开销，效率有提高了不少。我在C的基础上编写了D算法，D 算法采用并行计算技术，在我的双核笔记本电脑上数据量比较大的情况下，其排序效率较C要提高30%左右。 下面重点介绍这个并行排序算法。算法思路其实很简单，就是将要排序的数组按照处理器数量等分成若干段，然后用和处理器数量等同的线程并行对各个小段进行排序，排序结束和，再在单一线程中对这若干个已经排序的小段进行归并排序，最后输出完整的排序结果。考试大考虑到和.Net 2.0 兼容，没有用微软提供的并行库，而是用多线程来实现。 下面是测试结果： n A B C D 32768 0.7345 0.04122 0.0216 0.0254 65535 1.5464 0.08863 0.05139 0.05149 131072 3.2706 0.1858 0.118 0.108 262144 6.8423 0.4056 0.29586 0.21849 524288 15.0342 0.9689 0.7318 0.4906 1048576 31.6312 1.9978 1.4646 1.074 2097152 66.9134 4.1763 3.0828 2.3095 从测试结果上看，当要排序的数组长度较短时，并行排序的效率甚至还没有不进行并行排序高，这主要是多线程的开销造成的。当数组长度增大到25万以上时，并行排序的优势开始体现出来，随着数组长度的增长，排序时间最后基本稳定在但线程排序时间的 74% 左右，其中并行排序的消耗大概在50%左右，归并排序的消耗在 14%左右。由此也可以推断，如果在4CPU的机器上，其排序时间最多可以减少到单线程的 14 + 25 = 39%。8 CPU 为 14 + 12.5 = 26.5%。 目前这个算法在归并算法上可能还有提高的余地，如果哪位高手能够进一步提高这个算法，不妨贴出来一起交流交流。 下面分别给出并行排序和归并排序的代码： 并行排序类 ParallelSort 排序算法的比较 系统总体说明： 编程实现选择、冒泡、直接插入、折半插入、希尔、快速和归并等排序算法，并计算每种算法的比较、移动次数。 完成功能的详细说明： 1．要求由键盘输入待排序数据的个数和待排序数据。 2．实现选择、冒泡、直接插入、折半插入、希尔、快速和归并等排序算法。 3．比较每种排序算法在排序码个数相同的情况下，排序过程中排序码的比较次数和元素的移动次数。 4．待排序数据量分别取n=10，30，50，100时，比较同一个算法在排序过程中排序码的比较次数和元素的移动次数。 5．输出结果中，给出各算法按两种方式进行比较后的结果。#include void binsertsort(Data);//折半插入排序折半插入排序减少了比较次数而未改变移动次数void shellsort(Data);//希尔排序希尔排序是对直接插入排序的一种改进算法void selectsort(Data);//直接选择排序 void bubblesort(Data);//冒泡排序交换排序分冒泡排序和快速排序 void quicksort(Data&,int,int);//快速排序快速排序是对冒泡排序的一种改进 void quicksortx(Data); void towmerge(Data&,Data&,int,int,int);//二路归并排序算法 void mergepass(Data&,Data&,int);//一趟2路归并算法 void mergesort(Data,Data);//2-路归并算法 list(){} void display(Data); void show(int); Data getdata1(int); Data getdata2(); void play1(int); void play2(); void play3(); }; int list::remove=0; int list::compare=0; Data list::getdata1(int length) { Data data; data.length=length; srand((int)time(0)); for(int i=0;iC (++)内部排序汇总(快速排序&冒泡排序&堆排序&选择排序&插入排序&归并排序)
简单的归并排序算法例子
归并排序算法实现 (迭代和递归)
归并排序分治策略的设计与实现
分治算法实验(用分治法实现归并排序算法)
多种排序的并行算法(具体)
多路归并排序 外部排序算法
归并排序实验报告
归并排序算法的基本思想及算法实现示例
数据结构实验-归并排序算法
并行归并排序
大文件内容排序,多路归并排序算法
数据结构之归并排序
数据结构8645归并排序(非递归算法)
排序算法实验报告讲解
快速排序与归并排序算法及时间复杂度分析(C++)
并行排序算法
课程设计题目(排序)