归并排序-排序-算法第四版
2021/9/30 20:11:14
本文主要是介绍归并排序-排序-算法第四版，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
文章目录
- 1、原地归并的抽象方法
- 2、自顶向下的归并排序
- 3、关于自顶向下归并排序的改进
- 3.1、对小规模子数组使用插入排序
- 3.2、测试数组是否已经有序
- 3.3、不将元素复制到辅助数组
- 3、自底向上的归并排序
- 4、比较
1、原地归并的抽象方法
实现归并的一种直截了当的方法是将两个不同的有序数组归并到第三个数组中，即创建一个大小适当的数组然后将两个输入数组中的元素一个个从小到大放入这个数组中。
但是，当用归并将一个大数组排序时，我们需要进行多次归并，因此在每次归并是都创建一个新数组来存储排序结果会带来问题。我们更希望有一种原地归并的方法，这样就可以先将前半部分排序，在将后半部分排序，然后在数组中移动元素而不需要使用额外的空间。但实际上已有实现都非常复杂，尤其是和使用额外的空间的方法相比。
下面的代码它将所有元素复制到一个辅助数组中，在将归并的结果放回原数组中
/**
* 归并以排序的两个子数组
* @param a 数组
* @param lo 子数组1起始索引
* @param mid 子数组1终止索引，mid+1子数组2起始索引
* @param hi 子数组2终止索引
*/
private static void merge(Comparable[] a, int lo, int mid, int hi) {
// 将a[lo...mid]和a[mid+1...hi]归并
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
- 方法在归并时（第二个for循环）进行了4个条件判断
- 左边用尽，取右半边元素
- 右边用尽，取左半边元素
- 右半边当前元素小于左半边元素，取右半边元素
- 右半边当前元素大于等于左半边元素，取左半边元素
2、自顶向下的归并排序
下面这段递归代码是归纳证明算法能够正确地将数组排序的基础：如果它能够将两个子数组排序，它就能够通过归并两个子数组将整个数组排序。
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
/**
* 插入排序
* 思想：希尔排序的思想是使任意间隔h的元素都是有序的。这样的数组被称为h有序数组。
* 算法：
* 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
* 按增量序列个数k，对序列进行k 趟排序；
* 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
*/
public class Merge {
private static Comparable[] aux;
/**
* 排序方法
* @param a 实现了Comparable接口的待排序数组
*/
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
/**
* 对子数组排序
* @param a 数组
* @param lo 子数组索引起始
* @param hi 子数组索引终止
*/
private static void sort(Comparable[] a, int lo, int hi) {
// 把数组a[lo...hi]排序
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
// 左半边数组排序
sort(a, lo, mid);
// 右半边数组排序
sort(a, mid + 1, hi);
// 归本结果
merge(a, lo, mid, hi);
}
/**
* 归并以排序的两个子数组
* @param a 数组
* @param lo 子数组1起始索引
* @param mid 子数组1终止索引，mid+1子数组2起始索引
* @param hi 子数组2终止索引
*/
private static void merge(Comparable[] a, int lo, int mid, int hi) {
// 将a[lo...mid]和a[mid+1...hi]归并
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
/**
* 比较大小
* @param a 目标a
* @param b 目标b
* @return 返回布尔值
*/
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
/**
* 交换数组元素
* @param a 数组
* @param i 索引
* @param j 索引
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
/**
* 打印数组
* @param a 数组
*/
private static void show(Comparable[] a) {
// 单行打印数组
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
}
StdOut.println();
}
/**
* 测试数组是否已经有序
* @param a 带测试数组
* @return 测试结果: true-数组有序；false-数组无序
*/
public static boolean isSorted(Comparable[] a) {
// 测试数组是否已经有序
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i-1])) return false;
}
return true;
}
public static void main(String[] args) {
// 从标准输入读取字符串，将他们排序并输出
String[] a = StdIn.readAllStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
上面一段代码是我们分析归并排序的运行时间的基础，而归并排序是算法设计中分治思想的典型应用。
命题F。对于长度为N的任意数组，自顶向下的归并排序需要1/2NlgN至NlgN次比较
证明。令C(N)表示将一个长度为N的数组排序时所需要的比较次数。我们又C(0)=C(1)=0,对于N>0,通过递归的sort()方法我们可以由响应的归纳关系得到比较次数的上限：
C ( N ) ≤ C ( ⌈ N 2 ⌉ ) + C ( ⌊ N 2 ⌋ ) + N C(N)\le C(\lceil\frac{N}{2}\rceil)+C(\lfloor\frac{N}{2}\rfloor)+N C(N)≤C(⌈2N⌉)+C(⌊2N⌋)+N
右边第一项为数组左半部分排序所用的比较次数，第二项为数组右半部分排序所用的比较次数，第三项是归并所用的比较次数。因为归并所需的比较次数最少为 ⌊ N 2 ⌋ \lfloor\frac{N}{2}\rfloor ⌊2N⌋,比较次数的下限：
C ( N ) ≥ C ( ⌈ N 2 ⌉ ) + C ( ⌊ N 2 ⌋ ) + ⌊ N 2 ⌋ C(N)\ge C(\lceil\frac{N}{2}\rceil)+C(\lfloor\frac{N}{2}\rfloor)+\lfloor\frac{N}{2}\rfloor C(N)≥C(⌈2N⌉)+C(⌊2N⌋)+⌊2N⌋
当N为2的幂（即 N = 2 n N=2^n N=2n)且上限不等式的等号成立时我妈妈能够得到一个解。以为 ⌈ N 2 ⌉ = ⌊ N 2 ⌋ = 2 n − 1 \lceil\frac{N}{2}\rceil=\lfloor\frac{N}{2}\rfloor=2^{n-1} ⌈2N⌉=⌊2N⌋=2n−1，可以得到
C ( 2 n ) = 2 C ( 2 n − 1 ) + 2 n C(2^n)=2C(2^{n-1})+2^n C(2n)=2C(2n−1)+2n
两边同时除以 2 n 2^n 2n,可得
C ( 2 n ) 2 n = 2 C ( 2 n − 1 ) 2 n + 1 \frac{C(2^n)}{2^n}=\frac{2C(2^{n-1})}{2^n}+1 2nC(2n)=2n2C(2n−1)+1
用这个公式替换右边第一项，重复n-1遍可得
C ( 2 n ) 2 n = 2 C ( 2 0 ) 2 0 + n \frac{C(2^n)}{2^n}=\frac{2C(2^0)}{2^0}+n 2nC(2n)=202C(20)+n
将两边同时乘以 2 n 2^n 2n可以解得
C ( N ) = C ( 2 n ) = n 2 n = N l g N C(N)=C(2^n)=n2^n=NlgN C(N)=C(2n)=n2n=NlgN
对于一般的N，得到的准确值要复杂一些。但对比较次数的上下界不等式使用相同的方法不难证明前面所述的对于任意N的结论。这个结论对于任意输入值和顺序都成立。
分析：
这棵树正好有n层。对于0到n-1之间的任意k，自顶向下的第k层有 2 k 2^k 2k个子数组，没数组的长度为 2 n − k 2^{n-k} 2n−k,归并最多需要 2 n − k 2^{n-k} 2n−k次比较。因此每层的比较次数为 2 k ∗ 2 n − k = 2 n 2^k*2^{n-k}=2^n 2k∗2n−k=2n,n层总共为 n 2 n = N l g N n2^n=NlgN n2n=NlgN
命题G。对于长度为N的任意数组，自顶向下的归并排序最多需要访问数组6NlgN次。
证明。每次归并最多需要访问数组6N次（2N次用来复制，2N次用来讲排好序的元素移动回去，另外对多比较2N次），根据命题F即可得到这个命题的结果。
3、关于自顶向下归并排序的改进
3.1、对小规模子数组使用插入排序
用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题中方法的调用过于频繁，所有改进对它们的处理方法能改进整个算法。对排序来说，我们已经知道插入排序（或者选择排序）非常简单，因为很可能在小数组上比归并排序更快。使用插入排序处理小规模子数组（比如长度为15）一般可以将归并排序的运行时间缩短10%~15%
3.2、测试数组是否已经有序
我们可以添加一个判断条件，如果a[mid]小于a[mid+1],我们就认为数组是有序的并跳过merge()方法。
3.3、不将元素复制到辅助数组
我们可以节省将数组元素复制到用于归并的辅助数组所用的时间（单空间不行）。
改进后的代码如下
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
/**
* 插入排序
* 思想：希尔排序的思想是使任意间隔h的元素都是有序的。这样的数组被称为h有序数组。
* 算法：
* 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
* 按增量序列个数k，对序列进行k 趟排序；
* 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
*/
public class MergeImprovement {
// 阈值15，数组小于15使用插入排序
private static final int THRESHOLD = 15;
/**
* 排序方法
* @param a 实现了Comparable接口的待排序数组
*/
public static void sort(Comparable[] a) {
Comparable[] aux = a.clone();
sort(aux, a, 0, a.length - 1);
}
/**
* 对子数组排序
* @param src 辅助数组
* @param dest 结果数组
* @param lo 子数组索引起始
* @param hi 子数组索引终止
*/
private static void sort(Comparable[] src, Comparable[] dest, int lo, int hi) {
// 把数组a[lo...hi]排序
if ((hi - lo) < THRESHOLD) {
// 数组长度小于阈值，使用插入排序
insertion(dest, lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
// 左半边数组排序
sort(dest, src, lo, mid);
// 右半边数组排序
sort(dest, src, mid + 1, hi);
// 归本结果
if (less(src[mid], src[mid+1])) return;
merge(src, dest, lo, mid, hi);
}
private static void insertion(Comparable[] a, int lo, int hi) {
int N = a.length;
for (int i = lo; i <= hi; i++) {
for (int j = i ; j > lo && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
/**
* 归并以排序的两个子数组
* @param src 辅助数组
* @param src 结果数组
* @param lo 子数组1起始索引
* @param mid 子数组1终止索引，mid+1子数组2起始索引
* @param hi 子数组2终止索引
*/
private static void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) {
// 将a[lo...mid]和a[mid+1...hi]归并
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) dest[k] = src[j++];
else if (j > hi) dest[k] = src[i++];
else if (less(src[j], src[i])) dest[k] = src[j++];
else dest[k] = src[i++];
}
}
/**
* 比较大小
* @param a 目标a
* @param b 目标b
* @return 返回布尔值
*/
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
/**
* 交换数组元素
* @param a 数组
* @param i 索引
* @param j 索引
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
/**
* 打印数组
* @param a 数组
*/
private static void show(Comparable[] a) {
// 单行打印数组
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
}
StdOut.println();
}
/**
* 测试数组是否已经有序
* @param a 带测试数组
* @return 测试结果: true-数组有序；false-数组无序
*/
public static boolean isSorted(Comparable[] a) {
// 测试数组是否已经有序
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i-1])) return false;
}
return true;
}
public static void main(String[] args) {
// 从标准输入读取字符串，将他们排序并输出
String[] a = StdIn.readAllStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
3、自底向上的归并排序
递归实现的归并排序是算法设计中分治思想的典型应用。我们将一个大问题分隔称小问题分别解决，然后用所用小问题的答案来解决整个大问题。尽管我们考虑的问题是归并两个大数组，实际上我们归并的数组大多数都非常小。实现递归的另外一个方法是先归并微型数组，然后成对的归并得到的子数组，如此这般，直到我们将整个数组归并在一起。这种实现方法比标志的递归方法代码量少。
自底向上的代码试下：
...
/**
* 排序方法
* @param a 实现了Comparable接口的待排序数组
*/
public static void sort(Comparable[] a) {
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz + sz) {
for (int lo = 0; lo < N -sz; lo += sz + sz) {
merge(a, lo, lo + sz -1, Math.min(lo + sz + sz - 1, N -1));
}
}
}
...
// 其他代码都相同，参考上面代码
自底向上的归并排序会多次遍历整个数组，根据子数组大小进行两两归并。子数组的大小sz的初始值为1，每次加倍。最后一个子数组的大小是sz的偶数倍的时候才会等于sz（否则它会比sz小）。
命题H。对于长度为N的任意数组，自底向上的归并排序需要1/2NlogN至NlgN次比较，最多访问数组6NlgN次。
证明。处理一个数组的遍历数正好是 ⌈ l g N ⌉ \lceil lgN\rceil ⌈lgN⌉。每一遍会访问数组6N次，比较次数在N/2和N之间。
4、比较
-
当数组长度为2的幂时，自顶向下和自底向上的归并排序所有的比较次数和数组访问次数正好相同，只是顺序不同。其他时候，两种方法的比较和访问数组的次序会有所不同。
-
自底向上归并排序比较适合用链表组织的数据。
自顶向下和自底向上的方式实现任何分治类算法都很自然。归并排序告诉我们，当能够用其中一种方法解决一个问题的时候，你都应该试试另一种。你是系统像Merge.sort()中那样化整为零的方式解决问题，喜欢是希望像MergeBu.sort()中那样循序渐进低解决问题呢？
QQ:806797785
仓库地址：https://gitee.com/gaogzhen/algorithm
这篇关于归并排序-排序-算法第四版的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-06-26结对编程到底难不难？答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图，怎么办？
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗？
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡？
- 2024-05-31全网首发第二弹！软考2024年5月《软件设计师》真题+解析+答案！（11-20题）
- 2024-05-31全网首发！软考2024年5月《软件设计师》真题+解析+答案！（21-30题）
