通常我们见到的merge sort的思路是典型的分而治之divide and conquer策略:
1. 如果待排序序列为空,或者只有1个元素,结束
2. 否则,将序列一分为二,将两个子序列分别merge sort,再将两个排好的子序列merge
我们也可以从另外一个角度出发,序列中存在一些已经排好的片段,我们可以把这些排好的片段merge起来,不断重复直到序列排好(只含有一个排好的片段,亦即整个序列)
这种思路叫做natural merge sort。
例如下面的Haskell代码:
mergesort' = foldl merge [] . groupBy' (<=)
其中merge的实现非常简单:
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
早期的Haskell 标准库中的groupBy (<=) xs可以把xs分成若干已序的小片段,例如:
groupBy (<=) [1, 5, 2, 7, 8, 10] 的结果是 [[1, 5], [2, 7], [8, 10]]
但是最新的标准库这样不可以了,原因是groupBy 接受一个用于判断相等的函数,相等必须满足:自反性、传递性和对称性
亦即:
x = x
x = y, y = z 则 x = z
x = y 则 y = x
而小于等于显然不满足。故而我写了一个groupBy',用于切割已序片段:
groupBy' :: (a->a->Bool) ->[a] ->[[a]]
groupBy' _ [] = [[]]
groupBy' _ [x] = [[x]]
groupBy' f (x:xs@(x':_)) | f x x' = (x:ys):yss
| otherwise = [x]:r
where
r@(ys:yss) = groupBy' f xs
注意,这个算法可以近一步提高。我们遍历已序序列,不断使用merge,其实我们可以针对已序序列,两两merge,然后对其结果在迭代地两两merge,
这就是典型的bottom up merge sort的思路,算法改进如下:
mergesort = concat . mergePairs . groupBy' (<=) where
mergePairs (xs:ys:xss) = mergePairs ((merge xs ys) : (mergePairs xss))
mergePairs xss = xss
D. Knuth在TAOCP(计算机程序设计艺术)中,给出的略有不同,是一种2-way natural merge sort,思路有些类似quick sort
我们同时从一个序列的头部和尾部向中间检查:
1. 从头部取出一个最长的升序子序列;
2. 从尾部取出一个最长的降序子序列;
3. 将结果merge到一个目标序列的头部,然后重复1, 2,下次将结果merge到目标序列的尾部
4. 重复1, 2, 3,直到待排序序列已序(从头部取出的最长升序序列,就是整个序列)
相应的python代码如下:
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/sorting/merge-sort/src/n2_merge_sort.py
C代码:
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/sorting/merge-sort/src/n2_merge_sort.c
全部源代码可以在github下载。
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/sorting/merge-sort/src/NMergeSort.hs
PS: 我们不讨论merge sort的优劣或者和Quick sort PK, 具体讨论可参见wikipedia
http://en.wikipedia.org/wiki/Merge_sort
分享到:
相关推荐
通过merge-sort算法的实现,掌握外存算法所基于的I/O模型与内存算法基于的RAM模型的区别;理解不同的磁盘访问优化方法是如何提高数据访问性能的。
Merge Sort算法c++的实现。用的是VS2008
c++ 分治法合并排序 merge sort c语言 分治法合并排序 merge sort(将cout修改printf 加头文件include "stdio.h")
merge sort 排序 C++ merge sort 算法的C++实现
Merge Sort 算法的C语言实现 linux 下编译;windows下没试过,也许需要改头文件
void merge_sort(int A[],int p,int r) { int q; if(p) { q=(p+r)/2;//计算q的值,即将问题拆分成两个子问题; merge_sort(A,p,q); //左半边递归调用merge_sort,缩小问题规模 printf("\n"); //print_A(A...
归并排序(Merge sort)(台灣譯作:合併排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
斯坦福公开课算法1 merge sort 第一节
注意前面有“Insert sort:”或“Natural merge sort:”或“Quick sort:”等输出前缀,格式以上文程序为准。 输入样例 9 3 5 2 1 7 8 1 5 9 8 5 2 1 7 3 1 5 9 5 9 2 1 7 8 1 3 5 输出样例 Insert sort: 1 1 2 ...
void merge(int A[],int p,int q,int r);//合并排序算法 /************合并排序算法的实现******************/ int main() { int p,q,r; printf("合并排序算法的实现:\n"); printf("请输入p、q、r的值(输入...
排序——归并排序(Merge sort)
基于python的排序算法-归并排序Merge Sort
归并排序(Merge Sort)源码及运行示例
merge-sort code
C#,单向链表(Simply Linked List)的归并排序(Merge Sort)算法与源代码 归并排序法(3Merge Sort,以下简称MS)是分治法思想运用的一个典范。 其主要算法操作可以分为以下步骤: Step 1:将n个元素分成两个含n/...
算法分析与设计教学课件:Chapter 4 Merge Sort and Recursion.pptx
public class ExternalSort { public static int BUFFER_SIZE = 10; ... public File sort(File file) throws IOException { ArrayList<File> files = split(file); return process(files); }
sql学习 Merge Sort Join优化第4式(保证PGA尺寸).sql