本文共 2400 字,大约阅读时间需要 8 分钟。
归并(Merge)法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并是建立在归并操作上的一种有效的算法。该算法是采用(Divide and Conquer)的一个非常典型的应用。值得注意的是归并排序是一种的排序方法。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序,称为二路。
package com.mylearn.algorithm.sort; import org.apache.commons.lang.xwork.StringUtils; /** * Created by IntelliJ IDEA. * User: yingkuohao * Date: 13-9-25 * Time: 上午10:08 * CopyRight:360buy * Descrption: 归并排序,递归+分治 * 在求解一个输入规模为n,而n的取值又很大的问题时,直接求解往往非常困难。这时,可以先分析问题本身所具有的某些特性, * 然后从这些特性出发,选择某些适当的设计策略来求解。这种方法,就是所谓的分治法。 * * 适用条件: * 采用分治法解决的问题一般具有如下特征: * 1. 问题的规模缩小到一定规模就可以很容易解决。 * 2. 问题可以分解为若干个规模较小的模式相同的子问题,即该问题具有最优子结构性质。 * 3. 合并问题分解出的子问题的解可以得到问题的解。 * 4. 问题所分解出的各个子问题之间是独立的,即子问题之间不存在公共的子问题。 * * To change this template use File | Settings | File Templates. */ public class MergeSort { public static void main(String args[]) { Integer[] integers = new Integer[]{12, 15, 9, 24, 6, 31}; MergeSort mergeSort = new MergeSort(); System.out.println("初始:" + StringUtils.join(integers, ",")); integers = mergeSort.execute(integers); System.out.println("结果:" + StringUtils.join(integers, ",")); } /** * 分治法: * 1. 划分步: 把输入的问题划分为k个子问题,并尽量使这k个子问题的规模大致相同。 * 2. 治理步: 当问题的规模大于某个预定的阀值n0时,治理步由k个递归调用组成。 * 3. 组合步: 把各个子问题的解组合起来,它对分值算法的实际性能至关重要,算法的有效性很大地依赖于组合步的实现。 * @param integers * @return */ private Integer[] execute(Integer[] integers) { if (integers.length == 1) { return integers; } int center = integers.length / 2; //1.划分步:拆分左右数组 Integer[] left = new Integer[center]; Integer[] right = new Integer[integers.length - center]; //拷贝左右值 System.arraycopy(integers, 0, left, 0, center); System.arraycopy(integers, center, right, 0, right.length); //2. 治理步:递归调用 left = execute(left); right = execute(right); //3.组合步:左右排序 Integer[] result = sort(left, right); return result; } /** * 排序算法 * @param left * @param right * @return */ private Integer[] sort(Integer[] left, Integer[] right) { int i = 0, j = 0; Integer[] result = new Integer[left.length + right.length]; //循环遍历左右,比较大小, while (i < left.length && j < right.length) { if (left[i] < right[j]) { result[i + j] = left[i]; i++; } else { result[i + j] = right[j]; j++; } } //如果一侧的结果都比另一侧的某个值小,导致另一侧的结果没有copy到result中,需要重新拷贝剩余的值,由于左右两侧都是有序的,直接循环拷贝即可 if (i == left.length) { while (j < right.length) { result[i + j] = right[j]; j++; } } if (j == right.length) { while (i < left.length) { result[i + j] = left[i]; i++; } } return result; } } |
转载地址:http://yzrrb.baihongyu.com/