常用排序算法

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个关键字有序的序列。

衡量排序算法的两个指标，时间复杂度和稳定性。

举个例子，如果我们的数据是：3 5 4 2 2, 稳定的排序最后的俩个2在排好序后他们的原始前后顺序是不会变的，不稳定的排序最后两个2的顺序可能交换。

常见排序算法时间复杂度和稳定性：

时间复杂度曲线：

冒泡排序

冒泡排序是將比較大的數字移到序列的后面，较小的移到前面。

步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

实例

原始数据：

3 5 2 6 2

第一轮

比较 3 和 5，5 大于 3 ，不需交换

3 5 2 6 2

继续比较 5 和 2，5 大于 2，交换位置

3 2 5 6 2

继续比较 5 和 6，6 大于 5，不需交换

3 2 5 6 2

继续比较 6 和 2，6 大于 2，交换位置

3 2 5 2 6

6 移到最后，两个2都分别向前移动。

第二轮

比较 3 和 2， 3 大于 2，交换位置

2 3 5 2 6

比较 3 和 5， 5 大于 3，不需交换

2 3 5 2 6

比较 5 和 2， 5 大于 2，交换位置

2 3 2 5 6

不需比较 5 和 6

第三轮

比较 2 和 3， 3 大于 2，不需交换

2 3 2 5 6

比较 3 和 2， 3 大于 2，交换位置

2 2 3 5 6

不需比较了

第四轮

比较 2 和 2，不需交换

2 2 3 5 6

四轮结束

2 2 3 5 6

实现

public class Bubble {

    /**
     * 冒泡排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        int temp;
        // 第一层循环表明比较的轮数, 比如 length 个元素,比较轮数为 length-1 次（不需和自己比）
        for (int i = 0; i < array.length - 1; i++) {
            System.out.println("第" + (i + 1) + "轮开始");
            // 第二层循环，每相邻的两个比较一次，次数随着轮数的增加不断减少，每轮确定一个最大的，不需比较那个最大的
            for (int j = 0; j < array.length - 1 - i; j++) {
                System.out.println("第" + (i + 1) + "轮，第" + (j + 1) + "次比较：");
                if (array[j + 1] < array[j]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
                for (int k : array) {
                    System.out.print(k + " ");
                }
                System.out.println();
            }
            System.out.println("结果：");
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。

设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位，故在进行下一趟排序时只要扫描到pos位置即可。

public static int[] sort(int[] array) {
    int temp;
    int time = 1;
    for (int i = array.length - 1; i > 0;) {
        System.out.println("第" + time + "轮开始");
        int pos = 0;
        // 第二层循环，每相邻的两个比较一次，次数随着轮数的增加不断减少，每轮确定一个最大的，不需比较那个最大的
        for (int j = 0; j < i; j++) {
            System.out.println("第" + time + "轮，第" + (j + 1) + "次比较：");
            if (array[j + 1] < array[j]) {
                pos = j;
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        i = pos;
        time++;
        System.out.println("结果：");
        for (int k : array) {
            System.out.print(k + " ");
        }
        System.out.println();
    }
    return array;
}

快速排序

快速排序，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

步骤

选择一个基准元素，通常选择第一个元素或者最后一个元素
通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值均比基准值大
此时基准元素在其排好序后的正确位置
然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

实例

原始数据：

3 5 2 6 2

选择 3 作为基准

第一轮

从右往左找比3小的，最后一个2符合，将2和3对调

2 5 2 6 3

对调一次，查找的方向反向，从左向右找比3大的，5符合，对调

2 3 2 6 5

再从右往左找比3小的，2符合，对调

2 2 3 6 5

一轮结束

第二轮

对 [2 2] 采用同上的方式进行，得到

2 2 3 6 5

第三轮

对 [6 5] 采用同上的方式进行，得到

2 2 3 5 6

最终结果

2 2 3 5 6

快排是不稳定的排序，如上面原始的两个2的前后顺序发生了变化。

实现

public class Quick {

    private static int mark = 0;

    /**
     * 快排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        return quickSort(array, 0, array.length - 1);
    }

    /**
     * 辅助交换方法
     * 
     * @param array
     * @param a
     * @param b
     */
    private static void swap(int[] array, int a, int b) {
        if (a != b) {
            int temp = array[a];
            array[a] = array[b];
            array[b] = temp;
            // 找到符合的，对调
            System.out.println("对调" + array[a] + "与" + array[b] + ",得到");
            for (int i : array) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    /**
     * 新一轮分隔
     * 
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partition(int array[], int low, int high) {
        int base = array[low];
        mark++;
        System.out.println("正在进行第" + mark + "轮分隔，区域：" + low + "-" + high);
        while (low < high) {
            while (low < high && array[high] >= base) {
                high--;
                System.out.println("从右往左找比" + base + "小的，指针变动：" + low + "-" + high);
            }
            swap(array, low, high);
            while (low < high && array[low] <= base) {
                low++;
                System.out.println("从左往右找比" + base + "大的，指针变动：" + low + "-" + high);
            }
            swap(array, low, high);
        }
        return low;
    }

    /**
     * 对数组进行快速排序，递归调用
     * 
     * @param array
     * @param low
     * @param heigh
     * @return
     */
    private static int[] quickSort(int[] array, int low, int high) {
        if (low < high) {
            int division = partition(array, low, high);
            quickSort(array, low, division - 1);
            quickSort(array, division + 1, high);
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

直接插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

步骤

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置之后
重复步骤2，直到排好序为止

实例

原始数据：

3 5 2 6 2

第一轮，把 3 作为已经排好序的，取出 5 与 3 进行比较，5 大于 3 位置保持不变，新的有序组为 [3 5]

3 5 2 6 2

第二轮，取出第一个 2 ，从已排序的 [3 5] 数组从后往前比较，与 5 比较，小于 5，将 5 向后移动一个位置，再与 3 比较，小于 3，将 3 向后移动一个位置，前面没有了，将 2 放置在原来 3 的位置，新的有序组为 [2 3 5]

2 3 5 6 2

第三轮，取出 6 ，与 5 比较，5 保持不动，新的有序组 [2 3 5 6]

2 3 5 6 2

第四轮，取出 2 ，与 6 比较，6 向后移动一位，与 5 比较，5 向后移动一位，与 3 比较，3 向后移动一位，与 2 比较，不需移动，将取出的 2 放到原来 3 的位置即可，至此完成排序。

2 2 3 5 6

实现

public class StraightInsert {

    /**
     * 直接插入排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        // 将第一个i=0作为已排序组
        for (int i = 1; i < array.length; i++) {
            System.out.println("第" + i + "轮比较结果：");
            // 取出i索引待排序元素
            int temp = array[i];
            int j;
            // 从已排序数组后面往前逐个比较，确定i元素的位置，并将相应的元素后移一位
            for (j = i - 1; j >= 0 && temp < array[j]; j--) {
                array[j + 1] = array[j];
            }
            // 找到了位置
            array[j + 1] = temp;
            // 输出此轮排序结果
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

希尔排序

希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组，然后分别对划分出来的数组进行插入排序。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

步骤

取增量，一般取数组长度/2
按增量取得一个子数列，对子数列按插入排序的方式处理
将增量递减，重复1,2步骤
直至增量为为0，数列已经排好序

希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。

实例

原始数据：

3 5 2 6 2

取5/2=2作为增量，对[3 2 2]进行插入排序，得到

2 5 2 6 3

对[5 6]进行插入排序，得到

2 5 2 6 3

对[2 3]进行插入排序，得到

2 5 2 6 3

增量递减2/2=1，对[2 5 2 6 3]进行插入排序，得到

2 2 3 5 6

增量递减为0，排序结束。

直接插入排序是稳定的，但希尔排序是不稳定的。

举个例子，如果我们的数据是：3 5 4 2 2, 稳定的排序最后的俩个2在排好序后他们的原始前后顺序是不会变的，但是使用我们上面的希尔排序两个2的前后顺序会颠倒。

实现

public class Shell {

    /**
     * 希尔排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        int step = array.length / 2;
        while (step >= 1) {
            // 子插入排序
            for (int i = step; i < array.length; i++) {
                // 取出i索引待排序元素
                int temp = array[i];
                int j;
                // 从已排序数组后面往前逐个比较，确定i元素的位置，并将相应的元素后移step位
                for (j = i - step; j >= 0 && temp < array[j]; j -= step) {
                    array[j + step] = array[j];
                }
                // 找到了位置
                array[j + step] = temp;
            }
            System.out.println("增量为：" + step + ",结果：");
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
            step /= 2;
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

简单选择排序

在要排序的一组数中，选出最小的一个数与第1个位置的数交换；然后在剩下的数当中再找最小的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

步骤

从n 个记录中找出关键码最小的记录与第一个记录交换
从第2 个记录开始的 n-1 个记录中再选出最小的记录与第2 个记录交换
从第i (i是不断+1的)个记录开始的 n-i+1 个记录中选出最小的与第i 个记录交换
直到整个序列有序

实例

原始数据：

3 5 2 6 2

第一轮，找出 [5 2 6 2] 中最小的第一个 2 ，与第一个位置的 3 进行交换

2 5 3 6 2

第二轮，找出 [3 6 2] 中最小的 2 与第一轮中第二个位置的 5 进行交换

2 2 3 6 5

第三轮，找出 [6 5] 中最小的 5 与第二轮中第三个位置的 3 不需交换

2 2 3 6 5

第四轮，找出 [5] 中最小的 5 与第三轮中的第四个位置的 6 进行交换

2 2 3 5 6

第五轮，没有了，最终结果

2 2 3 5 6

简单选择排序也可以认为是稳定的排序。

简单选择排序是不稳定的，如果原始数据为3 3 2 6 2, 第一轮时两个3的位置就前后变化了。

实现

public class SimpleSelect {

    /**
     * 简单选择排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.println("第" + (i + 1) + "轮比较结果：");
            int minPosition = i;
            // 找出i之后的数组中的最小索引
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minPosition]) {
                    minPosition = j;
                }
            }
            // 判断是否需要调换位置
            if (array[i] > array[minPosition]) {
                int temp = array[i];
                array[i] = array[minPosition];
                array[minPosition] = temp;
            }
            // 输出此轮排序结果
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

改进

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。

public static int[] sortPlus(int[] array) {
    int minPosition, maxPosition;
    for (int i = 0; i <= array.length / 2; i++) {
        System.out.println("第" + (i + 1) + "轮比较结果：");
        minPosition = i;
        maxPosition = i;
        // 找出i之后的数组中的最小和最大索引
        for (int j = i + 1; j < array.length - i; j++) {
            if (array[j] < array[minPosition]) {
                minPosition = j;
            }
            if (array[j] > array[maxPosition]) {
                maxPosition = j;
            }
        }
        // 判断是否需要调换位置
        if (array[i] > array[minPosition]) {
            int temp = array[i];
            array[i] = array[minPosition];
            array[minPosition] = temp;
        }
        // 判断是否需要调换位置
        if (array[array.length - 1 - i] < array[maxPosition]) {
            int temp = array[array.length - 1 - i];
            array[array.length - 1 - i] = array[maxPosition];
            array[maxPosition] = temp;
        }
        // 输出此轮排序结果
        for (int k : array) {
            System.out.print(k + " ");
        }
        System.out.println();
    }
    return array;
}

堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

堆的定义如下：具有n个元素的序列(k1,k2,…,kn), 当且仅当满足:

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）或最大项（大顶堆）。

若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点（有子女的结点）的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。

(a)大顶堆序列：(96, 83, 27, 38, 11, 09)

(b)小顶堆序列：(12, 36, 24, 85, 47, 30, 53, 91)

步骤

初始时把要排序的n 个数的序列看作是一棵顺序存储的二叉树
调整它们的顺序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素。
然后对剩下的n-1个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。
依此类推，直到最后得到有n个节点的有序序列。

实例

实现堆排序需解决两个问题：

如何将n 个待排序的数建成堆；
输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

建堆方法（小顶堆）：

对初始序列建堆的过程，就是一个反复进行筛选的过程。

n 个结点的完全二叉树，则最后一个结点是第n/2个结点的子树。
筛选从第n/2个结点为根的子树开始（n/2是最后一个有子树的结点），使该子树成为堆。
之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程

无序序列：(49, 38, 65, 97, 76, 13, 27, 49)

(a) 无序序列，初始二叉树，97（第8/2=4个结点）为最后一个结点（49）的父结点。

(b) 97>=49,替换位置，接下来对8/2-1=3结点65进行筛选。

(d) 13<=38且49>=13,替换49和13的位置，49>=27,替换49和27的位置。

(e) 最终得到一个堆，13是我们得到的最小数。

调整堆的方法（小顶堆）：

设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶，堆被破坏，其原因仅是根结点不满足堆的性质。
将不满足堆的结点与左、右子树中较小元素的进行交换。
若与左子树交换：如果左子树堆被破坏，则重复方法(2).
若与右子树交换，如果右子树堆被破坏，则重复方法(2).
继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

调整堆只需考虑被破坏的结点，其他的结点不需调整。

堆排序也是不稳定的。

实现

public class HeapSort {

    /** 
     * 调整为小顶堆（排序后结果为从大到小）
     * 
     * @param array是待调整的堆数组 
     * @param s是待调整的数组元素的位置
     * @param length是数组的长度
     * 
     */
    public static void heapAdjustS(int[] array, int s, int length) {
        int tmp = array[s];
        int child = 2 * s + 1;// 左孩子结点的位置
        System.out.println("待调整结点为：array[" + s + "] = " + tmp);
        while (child < length) {
            // child + 1 是当前调整结点的右孩子
            // 如果有右孩子且小于左孩子，使用右孩子与结点进行比较，否则使用左孩子
            if (child + 1 < length && array[child] > array[child + 1]) {
                child++;
            }
            System.out.println("将与子孩子 array[" + child + "] = " + array[child] + " 进行比较");
            // 如果较小的子孩子比此结点小
            if (array[s] > array[child]) {
                System.out.println("子孩子比其小，交换位置");
                array[s] = array[child];// 把较小的子孩子向上移动，替换当前待调整结点
                s = child;// 待调整结点移动到较小子孩子原来的位置
                array[child] = tmp;
                child = 2 * s + 1;// 继续判断待调整结点是否需要继续调整

                if (child >= length) {
                    System.out.println("没有子孩子了，调整结束");
                } else {
                    System.out.println("继续与新的子孩子进行比较");
                }
            } else {
                System.out.println("子孩子均比其大，调整结束");
                break;// 当前待调整结点小于它的左右孩子，不需调整，直接退出
            }
        }
    }

    /** 
     * 调整为大顶堆（排序后结果为从小到大）
     * 
     * @param array是待调整的堆数组 
     * @param s是待调整的数组元素的位置
     * @param length是数组的长度
     * 
     */
    public static void heapAdjustB(int[] array, int s, int length) {
        int tmp = array[s];
        int child = 2 * s + 1;// 左孩子结点的位置
        System.out.println("待调整结点为：array[" + s + "] = " + tmp);
        while (child < length) {
            // child + 1 是当前调整结点的右孩子
            // 如果有右孩子且大于左孩子，使用右孩子与结点进行比较，否则使用左孩子
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
            System.out.println("将与子孩子 array[" + child + "] = " + array[child] + " 进行比较");
            // 如果较大的子孩子比此结点大
            if (array[s] < array[child]) {
                System.out.println("子孩子比其大，交换位置");
                array[s] = array[child];// 把较大的子孩子向上移动，替换当前待调整结点
                s = child;// 待调整结点移动到较大子孩子原来的位置
                array[child] = tmp;
                child = 2 * s + 1;// 继续判断待调整结点是否需要继续调整

                if (child >= length) {
                    System.out.println("没有子孩子了，调整结束");
                } else {
                    System.out.println("继续与新的子孩子进行比较");
                }
            } else {
                System.out.println("子孩子均比其小，调整结束");
                break;// 当前待调整结点大于它的左右孩子，不需调整，直接退出
            }
        }
    }

    /**
     * 堆排序算法
     * 
     * @param array
     * @param inverse true 为倒序排列，false 为正序排列
     */
    public static void heapSort(int[] array, boolean inverse) {
        // 初始堆
        // 最后一个有孩子的结点位置 i = (length - 1) / 2, 以此向上调整各结点使其符合堆
        System.out.println("初始堆开始");
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            if (inverse) {
                heapAdjustS(array, i, array.length);
            } else {
                heapAdjustB(array, i, array.length);
            }
        }
        System.out.println("初始堆结束");
        for (int i = array.length - 1; i > 0; i--) {
            // 交换堆顶元素H[0]和堆中最后一个元素
            int tmp = array[i];
            array[i] = array[0];
            array[0] = tmp;
            // 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
            if (inverse) {
                heapAdjustS(array, 0, i);
            } else {
                heapAdjustB(array, 0, i);
            }
        }
    }

    public static void main(String[] args) {
        int[] array = { 49, 38, 65, 97, 76, 13, 27, 49 };
        heapSort(array, false);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

}

归并排序

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间。

步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

实例

原始数据：

3 5 2 6 2

归并的前提是将数组分开，一分为二，再一分为二，分到不能再分，进行归并。

第一轮分隔，索引2 ((0+4)/2=2) 为中间

[3 5 2] [6 2]

第二轮分隔，对[3 5 2]进行分隔

[3 5] [2] [6 2]

第三轮分隔，对[3 5]进行分隔

[3] [5] [2] [6 2]

合并[3] [5]

[3 5] [2] [6 2]

合并[3 5] [2]

[2 3 5] [6 2]

第四轮分隔，对[6 2]进行分隔

[2 3 5] [6] [2]

合并[6] [2]

[2 3 5] [2 6]

合并[2 3 5] [2 6]

[2 2 3 5 6]

实现

public class Merge {

    private static int mark = 0;

    /**
     * 归并排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        return sort(array, 0, array.length - 1);
    }

    /**
     * 归并排序
     * 
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int[] sort(int[] array, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            mark++;
            System.out.println("正在进行第" + mark + "次分隔，得到");
            System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]");
            // 左边数组
            sort(array, low, mid);
            // 右边数组
            sort(array, mid + 1, high);
            // 左右归并
            merge(array, low, mid, high);
        }
        return array;
    }

    /**
     * 对数组进行归并
     * 
     * @param array
     * @param low
     * @param mid
     * @param high
     */
    private static void merge(int[] array, int low, int mid, int high) {
        System.out.println("合并:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]");
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (array[i] < array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        // 两个数组之一可能存在剩余的元素
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = array[j++];
        }
        // 把新数组中的数覆盖array数组
        for (int m = 0; m < temp.length; m++) {
            array[m + low] = temp[m];
        }
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}