归并排序思想:
以空间换取时间,不断地来回复制并且排序两个有序序列,直到排序完成。
递归到最底层后,可知道有序序列长度大小初始值为1,然后开始往回递归。
时间复杂度介于O(N)和O(N*logN)之间,空间复杂度O(N),是一种渐进最优算法。
这里采用的是分治策略。关于分治与递归,是比较有用的算法。
/**
* MergeSort.java 归并排序
*
* @author Administrator
*
*/
public class MergeSort {
public static void mergeSort(int[] a) {
int[] b = new int[a.length];
mSort(a, b, 0, a.length-1);
}
public static void mSort(int[] a, int[] b, int left, int right) {
if (left < right) { // 至少要有两个元素
int i = (left + right) / 2; // 取中点.
mSort(a, b, left, i);
mSort(a, b, i+1, right);
Util.merge(a, b, left, i, right); // 合并数组元素a[left:i]和a[left+1:right]至b[left:right]中.
Util.copy(a, b, left, right); // 把数组元素 b[left:right] 复制到 a[left:right]
}
}
public static void main(String[] args) throws Exception {
if (args.length == 0) {
System.out.println("请输入数字以空格隔开");
System.exit(-1);
}
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
a[i] = Integer.parseInt(args[i]);
mergeSort(a);
// 输出排序后的数组元素。
for (int i = 0; i < a.length; i++)
System.out.println(a[i]);
}
}
消除递归的合并排序:
http://thingkau.iteye.com/blog/235829
分享到:
相关推荐
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
数据结构排序选择排序归并排序基数排序PPT学习教案.pptx
C# 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
C++实现快速排序归并排序算法设计,用快速排序和归并排序算法,对记录进行排序。
//排序类 提供int排序的静态方法 有以下排序: 快速排序 堆排序 计数排序 桶排序 归并排序
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
归并排序
自己写的三个排序算法的比较。快速排序、归并排序、简单排序 对三个排序算法所消耗时间进行统计,比较时间效率 程序是在Linux下用C写的,vc下并未做测试。
随机产生1000个0~9的数,并分别用堆排序,快速排序,归并排序将产生的这1000个随机数排序,并将排序结果写入文件
java快速排序 归并排序 冒泡排序 选择排序
选择排序 归并排序 冒泡排序 堆排序 快速排序 等排序算法c++实现以及其效率比较 包括源代码
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
归并排序,比较高效的排序算法之一。这是一个例子,一个关于归并排序的例子。
冒泡排序 选择排序 插入排序 归并排序 快速排序 结构体排序(冒泡排序+结构体的应用) 桶排序 二分查找 DFS深搜 c++基础语法+基础算法 c++算法初阶者使用
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
数据结构课件:第10章 排序2选择排序归并排序基数排序.pptx
printf("\t6: 归并排序\n"); printf("\t7: 希尔排序\n"); printf("\t***************************\n"); scanf("%d",&i); //输入整数1-7,选择排序方式 switch (i){ case 1: InsertSort(R); break; //值为1,...
双指针算法,Python双指针算法模板和题目同向相向快速排序归并排序