核心代码：
public static void unRecursiveMergeSort(int[] a, int n) { int low = 0, high = 0, mid = 0; // 待归并数组长度，1 2 4 8 ... int len = 1; // 从最小分割单位 1 开始 while(len <= n) { // 按分割单位遍历数组并合并 for (int i = 0; i + len <= n; i += len * 2) { low = i; // mid 变量主要是在合并时找到右半边数组的起始下标 mid = i + len - 1; high = i + 2 * len - 1; // 防止超过数组长度 if (high > n - 1) { high = n - 1; } // 归并两个有序的子数组 merge(a, low, mid, high); } len *= 2; // 增加切分单位 } }算法分析：
平均时间复杂度，最佳和最差情况都是 O(nlgn)
空间复杂度 O(n)，需要一个大小为 n 的临时数组
归并排序也是一个稳定的排序算法
6. 快速排序快排可以说是应用最广泛的算法了，它的特点是使用很小的辅助栈原地排序。它也是一个分而治之的排序算法，基本思想是：选取一个关键值，将数组分成两部分，一部分小于关键值，一部分大于关键值，然后递归的对左右两部分排序。过程如下：
选取 a[low] 作为关键值-切分元素 p
使用两个指针遍历数组（既可一前一后，也可同方向移动），将比 p 小的元素前移，最后交换切分元素
递归的对左右部分进行排序
递归实现快排核心代码：
public static void quickSort(int[] a, int low, int high) { if (low < high) { int m = partition(a, low, high); // 切分 quickSort(a, low, m-1); // 将左半部分排序 quickSort(a, m+1, high); // 将右半部分排序 } } public static int partition(int[] a, int low, int high) { // 将数组切分为 a[low..i-1], a[i], a[i+1..high] int p = a[low]; // 切分元素 int i = low; // 下一个小于切分元素可插入的位置 // 从切分元素下一个位置开始，遍历整个数组，进行分区 for (int j = low + 1; j <= high; j++) { // 往前移动比切分元素小的元素 if (a[j] < p && (i++ != j)) { int tmp = a[j]; a[j] = a[i]; a[i] = tmp; } } // 交换中枢(切分)元素 int tmp = a[low]; a[low] = a[i]; a[i] = tmp; return i; }算法分析：
平均时间复杂度 O(nlgn)，最佳情况 O(nlgn)，最差情况是 O(n^2)
空间复杂度 O(lgn)，因为递归，占用调用栈空间
快排是一个不稳定的排序算法
7. 堆排序堆排序是利用堆这种数据结构设计的算法。堆可看作一个完全二叉树，它按层级在数组中存储，数组下标为 k 的节点的父子节点位置分别如下：
k 位置的父节点位置在 (k-1)/2 向下取整
k 位置的左子节点位置在 2k+1
k 位置的右子节点位置在 2k+2
堆的表示如下：
堆有序的定义是每个节点都大于等于它的两个子节点，所以根节点是有序二叉堆中值最大的节点。堆排序就是一个不断移除根节点，使用数组剩余元素重新构建堆的过程，和选择排序有点类似（只不过按降序取元素），构建堆有序数组基本步骤如下：
首先使用 (N-1)/2 之前的元素构建堆，完成后，整个堆最大元素位于数组的 0 下标位置
把数组首尾数据交换，此时数组最大值以找到
把堆的尺寸缩小 1，重复步骤 1 和 2，直到堆的尺寸为 1
核心代码：
public static void heapSort(int[] a) { int n = a.length - 1; // 构建堆，一开始可将数组看作无序的堆 // 将从下标为 n/2 开始到 0 的元素下沉到合适的位置 // 因为 n/2 后面的元素都是叶子结点，无需下沉 for (int k = n/2; k >= 0; k--) sink(a, k, n); // 下沉排序 // 堆的根结点永远是最大值，所以只需将最大值和最后一位的元素交换即可 // 然后再维护一个除原最大结点以外的 n-1 的堆，再将新堆的根节点放在倒数第二的位置，如此反复 while (n > 0) { // 将 a[1] 与最大的元素 a[n] 交换，并修复堆 int tmp = a[0]; a[0] = a[n]; a[n] = tmp; // 堆大小减1 n--; // 下沉排序，重新构建 sink(a, 0, n); } } /** 递归的构造大根堆 */ private static void sink(int[] a, int k, int n) { // 是否存在左孩子节点 while ((2*k+1) <= n) { // 左孩子下标 int left = 2*k+1; // left < n 说明存在右孩子，判断将根节点下沉到左还是右 // 如果左孩子小于右孩子，那么下沉为右子树的根，并且下次从右子树开始判断是否还要下沉 if (left < n && a[left] < a[left + 1]) left = left + 1; // 如果根节点不小于它的子节点，表示这个子树根节点最大 if (a[k] >= a[left]) break; // 不用下沉，跳出 // 否则将根节点下沉为它的左子树或右子树的根，也就是将较大的值上调 int tmp = a[k]; a[k] = a[left]; a[left] = tmp; // 继续从左子树或右子树开始，判断根节点是否还要下沉 k = left; } }算法分析：
平均时间复杂度、最佳和最坏均是 O(nlgn)
空间复杂度 O(1)，原地排序
不稳定的排序算法
8. 小结