每篇笔记都会附上随书的Applet演示程序,有算法看不明白的,可以下载Applet运行起来(直接打开html文件即可),可以很容易地看清楚算法的每一步。
方法调用自身,就构成了
递归调用,通常递归都有个终止条件,否则程序无法停止运行。
归并排序
归并排序的原理(升序排序)是将两个有序数组合并成一个有序数组,先对比两个数组的
第1项,如果
数组a的第1项大于
数组b的第1项,那么将
数组b的第1项复制到新数组中。接着对比
数组a的第1项和
数组b的第2项,再把更小的一项放到
新数组的第2个位置上……直到合并完成。
递归的过程是一个不断分割数组的过程,把原数组不断的分割成两半,直到不能再分割(长度为1),则返回,然后开始合并。
代码如下:
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] array){
T[] workspace = (T[])new Comparable[array.length];
recallMergeSort(array, workspace, 0, array.length - 1);
}
private static <T extends Comparable<? super T>> void recallMergeSort
(T[] array, T[] workspace, int lowerBound, int upperBound){
if(upperBound == lowerBound){
return;
}else{
int midIndex = (upperBound + lowerBound) / 2;
recallMergeSort(array, workspace, lowerBound, midIndex);
recallMergeSort(array, workspace, midIndex + 1, upperBound);
merge(array, workspace, lowerBound, midIndex + 1, upperBound);
}
}
private static <T extends Comparable<? super T>> void merge
(T[] array, T[] workspace, int lowerIndex, int higherIndex, int upperBound){
int i = 0;
int midIndex = higherIndex - 1;
int lowerBound = lowerIndex;
while(lowerIndex <= midIndex && higherIndex <= upperBound){
if(array[lowerIndex].compareTo(array[higherIndex]) < 0)
workspace[i++] = array[lowerIndex++];
else
workspace[i++] = array[higherIndex++];
}
while(lowerIndex <= midIndex)
workspace[i++] = array[lowerIndex++];
while(higherIndex <= upperBound)
workspace[i++] = array[higherIndex++];
for(i=lowerBound; i<=upperBound; i++)
array[i] = workspace[i - lowerBound];
}
归并排序的时间复杂度是O(N*logN),比表插入排序法快得多,但需要
多1倍的内存空间。对长度为1万的数组排序,时间几乎算不出来(几乎为0),因为我把数组扩大10倍,经测试,对随机数组进行排序需要0.094秒,逆序排序需要0.11秒。
分享到:
相关推荐
(10)数据结构之红黑树(三)——删除操作 (11)排序算法(一)——冒泡排序及改进 (12)排序算法(二)——选择排序及改进 (13)排序算法(三)——插入排序及改进 (14)排序算法(四)——归并排序与递归...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
非递归归并排序.cpp
java 数据结构 递归 八皇后 完美递归 java 数据结构 递归 八皇后 完美递归
JAVA数据结构与算法课程第05课双端链表和双向链表.mp4JAVA数据结构与算法课程第06课递归的应用.mp4JAVA数据结构与算法课程第07课递归的高级应用.mp4JAVA数据结构与算法课程第08课希尔排序.mp4JAVA数据结构与算法课程...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
算法思想——递归与分治 算法思想——递归与分治
用函数实现归并排序(非递归算法),并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个空格分隔 Sample...
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...
c语言分治法求众数重数-五大常见算法策略之——递归与分治策略,算法数据结构 五大常用算法
介绍了计算机编程中使用的...《Java数据结构和算法》(第2版)提供了学完一门编程语言后进一步需要知道的知识。本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程,在学生掌握了编程的基础后才开始本书的学习。
归并排序,消除递归归并排序,快排,Java实现
数据结构和算法学习之递归
c++实现的合并排序算法 用递归和非递归两种方式实现的
C语言版 数据结构与算法课程 第5章 递归算法(共77页).pptx C语言版 数据结构与算法课程 第6章 二叉树(共117页).ppt C语言版 数据结构与算法课程 第7章 树和森林(共61页).ppt C语言版 数据结构与算法课程 第8章...
以下是关于Java数据结构和算法的一些介绍: Java作为一种流行的编程语言,在数据结构和算法的实现方面有着广泛的应用。数据结构指的是在计算机中组织和存储数据的方式,算法则是明确定义的解决特定问题的规则和步骤。...
非递归归并排序详细分析,Java实现. 非常详细,基本上可以看明白
分治法排序算法