首页 > 代码库 > 普林斯顿大学算法课 Algorithm Part I Mergesort 归并排序
普林斯顿大学算法课 Algorithm Part I Mergesort 归并排序
起源：冯·诺依曼最早在EDVAC上实现
基本思想：
- 将数组一分为（Divide array into two halves）
- 对每部分进行递归式地排序（Recursively sort each half）
- 合并两个部分（Merge two halves）
归并排序体现的是一种分治思想（Divide and conquer）
演示：
1. 给出原数组a[]，该数组的lo到mid，mid+1到hi的子数组是各自有序的。
2. 将数组复制到辅助数组（auxiliary array）中，给两部分的首元素分别以i和j的下标，给原数组首元素以k的下标
3. 比较i下标和j下标的元素，将较小值赋到k下标位置的元素内，然后对k和赋值的下标进行递增；
该演示里j下标的元素比较小，于是将A赋到k的位置里，再对k和j递增，即j+1, k+1
4. 重复上述过程，直到比较完全部元素。
在Java中的实现
public class Merge{ private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { assert isSorted(a, lo ,mid); //检查a[lo..mid]是否有序 assert isSorted(a, mid + 1, hi); //检查a[mid+1..hi]是否有序 for(int k = lo; k <= hi; k++) //复制数组 aux[k] = a[k]; int i = lo, j = mid + 1; 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++]; } assert isSorted(a, lo, hi); } private static void sort(Comparable[] a, Comparable[] aux, int low, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid + 1, hi); merge(a, aux, lo, mid, hi); } public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, aux, 0, a.length - 1); }}
注：Assert（断言）功能：检查表达式内的值，若为true,则程序正常运行，若为false，则抛出异常，终止运行。
性能分析：
算法复杂度为N*log(N)
优化：
问题：归并排序需要根据数组大小N开辟额外的内存
原地算法（in-place Algorithm）：占用额外空间小于等于c log(N)的排序算法。
插入排序、选择排序、希尔排序都属于原地算法。归并排序不属于原地算法。Wiki参考
Kronrod在1969年发明了原地归并排序（in-place merge），不过看起来好像不是那么有用（Challenge for the bored）
实践上的改善（practical improvements）
改善1：对小数组使用插入排序
- 归并排序要为小的子数组的开辟投入很多开销（开辟数组除了元素占用内存，数组本身还有固定的开销）
- 当子数组大小超过7，停止（Cutoff）使用插入排序
private static void sort(Comparable[] a, Comparable[] aux, int low, int hi){ if （hi <= lo + CUTOFF - 1) { Insertion.sort(a, lo, hi); return; } int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid + 1, hi); merge(a, aux, lo, mid, hi);}
改善2：当数组排序好时，停止计算
- 两部分都已经排序完毕后，若前半部分的最后一个元素大于后半部分的第一个元素，则证明整个序列都是有序的。
private static void sort(Comparable[] a, Comparable[] aux, int low, int hi){ if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid + 1, hi); if (!less(a[mid + 1], a[mid])) return; merge(a, aux, lo, mid, hi);}
普林斯顿大学算法课 Algorithm Part I Mergesort 归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。