算法导论第2章(二) merge 排序
算法导论第2章(2) merge 排序
合并排序 (merge sort)
Merge排序的思想
合并排序是“分治法”的一个例子,它的主要思想就是:分解问题到若干个更小规模的问题,解决这些小规模问题,然后把小规模的问题合并,得到大规模问题的解。
合并排序也是这样子的:
分解:将n个元素的排序分解为两个n/2个元素的排序
解决:用合并排序法对这两个子序列进行递归的排序
合并:将两个排好序的子序列进行合并得到排序结构
合并排序的核心是函数 merge(s,p,q,r)
参数s是一个数列,p,q,r是数列s的三个元素的下表,满足p<=q<r
其中s[p…q]和s[q+1,r]都是排好序的,merge函数的作用就死将s[p…q]和s[q+1,r] 进行合并成一个排好序的数组并且替换s[p…r].
Merge排序的java实现
package com.junjun.algorithm.charpter2; import com.junjun.algorithm.Sort; /** * 归并排序 * @author buptjunjun * */ public class MergeSort extends Sort { @Override public int[] sort(int[] s, int incOrDec) { this.mergeSort(s,0, s.length-1); return s; } /** * 对数组 s进行归并排序,p<<q<r * 其中p到s[p,q] 和s[q+1,r]都是排好序的,将他们合并成一个排好序的数组并替换s[p,r] * @param s 数组 * @param p * @param q * @param r */ private void merge(int [] s,int p,int q,int r) { int n1 = q-p+1; //左边一段s[p,q]的长度 int n2 = r-q; //右边一段s[q+1,r]的长度 //多分配一个元素作为哨兵 int [] L = new int [n1+1]; int [] R = new int [n2+1]; for(int i = 0; i < n1;i++) L[i] = s[p+i]; for(int i = 0; i < n2; i++) R[i] = s[q+1+i]; //最后一个元素哨兵 L[n1] = Integer.MAX_VALUE; R[n2] = Integer.MAX_VALUE; // 开始归并 int i =0; int j = 0; int cadidate = 0; for(int k = p; k <= r; k++) { // 选择较小的作为插入对象 if(L[i] < R[j]) { cadidate = L[i]; i++; } else { cadidate = R[j]; j++; } //插入 s[k] = cadidate; } } /** * 递归进行merge排序 * @param s * @param p * @param r */ private void mergeSort(int [] s, int p ,int r) { if(p>=r) return; int q = (p+r)/2; mergeSort(s,p,q); mergeSort(s,q+1,r); merge(s,p,q,r); } /** * @param args */ public static void main(String[] args) { int [] s = {2,5,3,1,1,3,4,4,9,0}; int [] ret = new InsertSort().sort(s,Sort.INCREMENT); new InsertSort().print(s); } }
归并排序的时间复杂度分析:
假设有n个元素的数列进行归并排序,归并排序在这n个数上建立了一棵二叉树,
如下所示,是对8个数进行排序的例子
由N个元素的二叉树的深度是log2N+1,例如上面的树的深度是log28+1=3+1=4.
每一层进行合并的时间复杂度是线性的(merge 函数的时间复杂度是线性的),所以每一层的复杂度可以使用cN表示。
那么整个算法的时间复杂度就是cN(logN+1) = cNlogN+cN.忽略掉系数和低次项,得到时间复杂度为NlogN。