闲聊几句,先说说我为什么要写这些东西,有人说是炒冷饭,呵呵,其实本意是为了锻炼自己的写作能力,希望能把一个知识点深入浅出的表达出来,说着容易,但是对于一个新手,则需要一个很长的过程,之前一直没有意识到这块儿的薄弱性,所以打算通过写技术blog来锻炼自己,二是为了梳理一下自己的知识结构体系,三是为了分享自己的心得。所以刚刚开始时,难免文章有生硬的地方,打个比方,很可能写的东西,网上已经有很多类似的文章,并且总结的很好,图文并茂,看了之后 ,总有拷贝的冲动,但是里边总会有自己的体会,记录一下思想,以后再回顾的时候,一看,哦,当初是这样思考的,这个过程,我认为才是最重要的,所以即便是炒冷饭,我也要冷饭硬炒 !
开始今天的学习,归并排序,本来打算跟快速排序一起写,发现效果不好,本着一篇文章一个知识点的初衷,这里我先单介绍一下归并排序,回头在写一篇关于各个排序的对比和选择:
1。归并排序
定义:也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作,属于分治法(Divide and Conquer)的一个非常典型的应用。
基本思路:
-
Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。
-
Conquer: 对这两个子序列分别采用归并排序。
-
Combine: 将两个排序好的子序列合并成一个最终的排序序列
数组的代码实现:
public void mergeSort(int[] data, int left, int right) {
if (left < right) {
int mid = (left + right) >>> 1;
// 对左半部份排序
mergeSort(data, left, mid);
// 对有半部分排序
mergeSort(data, mid + 1, right);
// 合并到一个临时数组,再拷贝到data中
merge(data, left, mid, right);
}
}
public void merge(int[] data, int left, int mid, int right) {
int mergeleft, mergeright, index;
int[] temp = new int[right - left + 1];
mergeleft = left;
mergeright = mid + 1;
index = 0;
// 选择排序
while ((mergeleft <= mid) && (mergeright <= right)) {
if (data[mergeleft] < data[mergeright]) {
temp[index++] = data[mergeright++];
} else {
temp[index++] = data[mergeleft++];
}
// 剩下的数据拷贝到temp中
for (int rest = mergeleft; rest < mid; rest++) {
temp[index] = data[rest];
}
for (int rest = mergeright; rest < right; rest++) {
temp[index] = data[rest];
}
int pos = left;
for (index = 0; index < data.length; index++) {
data[pos] = temp[index];
}
}
再看下JDK中对象排序的实现,Arrays.sort(int[] a):
public static void sort(Object[] a) {
Object[] aux = (Object[])a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// 如果数组的长度小于7,则采用插入排序
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
这里我们看到对对象的排序采用的是归并算法,大体流程跟数组排序是一样的,只不过待排序对象数组要实现Comparable接口 。
2.时间复杂度分析
比较操作的次数介于(nlogn) / 2和nlogn − n + 1。 赋值操作的次数是(2nlogn)。 归并算法的空间复杂度为:Θ (n)
3.总结
如果大家看完上边的代码,感觉没有理解的话,建议把代码拷贝到IDE里边,DEBUG一下,一步一步的跟踪,也许这样你会比较深刻的理解分治法的思想,网上有很多归并算法的图形演示,但是刚开始的时候如果你看图,再学习代码,会有种分裂的感觉,至少我是这样,所以如果最后实在理解不了,也不要钻牛角尖,毕竟只是一个算法,大家只要理解其思想就可以了,或者我们能在实际编程中使用就行。
简单总结一下代码实现,对已有的数据序列,首先利用递归(网上没有看到用迭代方式实现的JAVA代码)逐层等分序列,直到最后只剩下两个一对的集合,然后开始逐层向上先排序再合并,期间的每次合并都需要一个中间的临时数组,直到合并为初始数组,这是所有的数据为已排序状态。这里我就不再画图了,网上有很多例子,感兴趣可以用google搜索一下。
最后上传一个GIF图片,提高一下感性认识,此图片来源于维基百科
随机点的进行归并排序
http://zh.wikipedia.org/zh-cn/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
- 大小: 13.1 KB
分享到:
相关推荐
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
算法-数据结构之归并排序.rar
1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、基数排序、快速排序、归并排序。(快速排序、归并排序讲到之后再做) 3、*能够显示各种排序算法的中间过程。
使用MFC单文档实现数据结构8种排序算法的图形界面动态演示,更加形象的展示排序过程,八种排序算法包括插入排序(直接插入排序、折半插入排序、希尔排序)、选择排序(直接选择排序、堆排序)、交换排序(冒泡排序、...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度,然后以表格的形式,清晰直观的表现出它们的复杂度的...
合并排序(MERGE SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个...
归并排序 经典数据结构算法 ppt.
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……
合并排序 数据结构 排序算法
数据结构中的内部排序法 归并排序 非常的好用
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
数据结构,合并排序算法.程序正确简单易懂。程序简单易懂哦。
归并排序 实验题目:归并排序 实验要求:对输入的一组数据利用归并排序算法进行排序并输出 1 需求分析 本实验要求对输入的一组数据利用归并排序算法进行排序并输出。 归并排序是利用归并过程的算法。所谓归并,是指...
随机产生1000个0~9的数,并分别用堆排序,快速排序,归并排序将产生的这1000个随机数排序,并将排序结果写入文件
快速排序,基数排序,插入排序,希尔排序,堆排序,归并排序等算法对数排序的时间进行比较。可以对5000000以内(超大数据量)的随机数(可能存在超大数值)进行排序!!!
内部排序算法主要分为5 大类,有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括:插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、...
总结的不错,值得一看 * 1.插入排序(直接插入排序、折半插入排序、希尔排序); * 2.交换排序(冒泡泡排序、快速排序); * 3.选择排序(直接选择排序、堆排序);...归并排序; * 5.基数排序。
用函数实现归并排序(非递归算法),并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个空格分隔 Sample...