问题描述写在了代码中,注释可以帮助理解
import java.util.ArrayList;
/**
* @author xusulong
* merge sort
* 分解:将n个元素分成各含/2个元素的子序列
* 解决:用merge sort对两个子序列递归地排序
* 合并:合并两个已排序的子序列以得到排序结果
*/
public class MergeSort {
private final static int max = 1000000;
/**
* 对子数组A[p...r]进行排序
* @param A
* @param p
* @param r
*/
public static void mergeSort(ArrayList<Integer> A, int p, int r) {
//当p = r 时候数组中只有一个元素,不需要排序,而p不可能大于r
if(p < r) {
int q = (p + r)/2;
mergeSort(A, p, q);
mergeSort(A, q + 1, r);
merge(A, p, q, r);
}
}
/**
*
* @param A 数组
* @param p 下标
* @param q 下标
* @param r 下标
* 假设子数组a[p...q]和a[q + 1...r]已经排序好 p <= q < r
*/
public static void merge(ArrayList<Integer> A, int p, int q, int r) {
//length of the child array
int n1 = q - p + 1;
int n2 = r - q;
//create arrays L[1...n1 + 1] and R[1...n2 + 1]
ArrayList<Integer> L = new ArrayList<Integer>(n1 + 1);
ArrayList<Integer> R = new ArrayList<Integer>(n2 + 1);
for(int i = 0; i < n1; i ++) {
L.add(A.get(p + i));
}
L.add(max);
for(int i = 0; i < n2; i ++) {
R.add(A.get(q + i + 1));
}
R.add(max);
for (int i = 0, j = 0, k = p; k <= r; k ++) {
if (L.get(i) <= R.get(j)) {
A.set(k, L.get(i));
i ++;
} else {
A.set(k, R.get(j));
j ++;
}
}
}
public static void main(String[] args) {
ArrayList<Integer> A = new ArrayList<Integer>();
A.add(4);
A.add(2);
A.add(5);
A.add(7);
A.add(0);
A.add(3);
A.add(1);
A.add(6);
mergeSort(A, 0, A.size() - 1);
System.out.println(A);
}
}
时间复杂度cnlog2n + cn 为 O(nlog2n)
分享到:
相关推荐
根据算法导论实现的归并排序算法
def merge(A, p, q, r): n1 = q - p + 1 n2 = r - q L = list(range(n1 + 1)) R = list(range(n2 + 1)) for i in range(0, n1): L[i] = A[p + i] for j in range(0, n2): R[j] = A[q + j + 1] ...
请参考算法导论第三版英文版Introduction to Algorithms 3rd Edition,本程序为第一章到第...归并排序 堆排序 快速排序(2中分割方法) 随机化快速排序 TAIL-RECURSIVE-QUICKSORT Counting sort Radix sort 二分法搜索
用C++实现归并排序,题目基于MIT的算法导论中的第二章中的归并排序算法要求,visual studio 2010 实现
包括源码:常用排序算法(插入、堆、归并、快速)、装配线问题、最长公共子序列问题、矩阵连乘问题、 优先队列、huffman编码、贪心算法,全部用Java实现的。 算法导论答案
用递归实现归并排序,利用算法导论书籍推荐归并算法,来简单实现归并排序
27.3 多线程归并排序 思考题 本章注记 第28章 矩阵运算 28.1 求解线性方程组 28.2 矩阵求逆 28.3 对称正定矩阵和最小二乘逼近 思考题 本章注记 第29章 线性规划 29.1 标准型和松弛型 ...
对于这一过程的理解,算法导论中给出了一个形象的模型。 即假设桌面上有两堆已排序好的的牌,且每一堆都正面朝下放置。然后我们分别从两堆牌中选取顶上的一张牌(选取之后,堆顶端又会露出新的顶牌),选取较小的...
实现归并排序的c++代码,根据算法导论书籍内伪代码改写
包含算法导论/数据结构中各种常用的排序算法:快速排序 冒泡排序 堆排序 选择排序 归并排序 插入排序 二分插入排序 希尔排序 计数排序 基数排序 桶式排序
github:还有除了算法导论外一些基础知识的笔记 我们能做到的排序有多快? 速度取决于计算模型【哪些操作是被允许的】 比较排序的算法模型 在模型中只能进行两两之间的大小比较来决定顺序 快速排序 归并排序 插入...
排序算法是基于《算法导论》一书的伪代码在 javascript中实现的。 实现的算法列表是: 插入排序。 堆插入排序。 合并排序。 优化归并排序。 堆排序。 快速排序。 随机快速排序。 计数排序。 该应用程序能够通过用户...
冒泡,插入,归并,堆排序算法代码,可运行,参照算法导论的数编程实现的
排序算法(插入、选择、归并、冒泡、堆排序)实现代码C++ ----根据《算法导论》中的伪代码,自己写的C++代码实现;
,部分算法来源于CLRS算法导论相关章节,在此向CLRS等诸位先驱致敬! advanced包相关: 为先进算法和数据结构相关内容,包含 1.b-tree的实现,以及文本数据库的简易实现 2.斐波那契堆的实现 ods包为开源数据库的源码...
1) 冒泡排序2)桶排序3) 鸡尾酒排序4) 梳状排序5) 计数排序6) 堆排序7) 插入排序8) 归并排序9) 快速排序10) 基数排序11) 选择排序12) 壳排序 代码的编写方式使得它可以很容易地翻译成其他语言(例如,每个实现在 C++...
排序算法(插入、选择、归并、冒泡、堆排序)实现代码C++ ----根据《算法导论》中的伪代码,自己写的C++代码实现; 新加入快速排序,和快速排序随机版
归并排序 chapter 3 最大子数组问题 chapter 6 堆 数据结构 堆排序 chapter 7 快速排序 快速排序(随机增强版) chapter 8 计数排序 桶排序 基数排序 chapter 9 期望为线性时间的选择算法(基于快排思想) 最坏为 O...