数组排序小结（对应：NC140 排序 LC912 排序数组）

参考资料：算法第4版，内容包括选择排序、插入排序、归并排序、快速排序和堆排序

[toc]

1. 初级排序算法

1.1 选择排序

遍历数组 (0~n)，找出最小元素，将最小元素和索引为0的元素交换；

遍历剩下的数组 (1~n)，找出最小元素，将最小元素和索引为1的元素交换；

重复上述过程，直到将整个数组排序完成。

特点：

运行时间和输入无关，即长度相等的有序数组和无序数组所需要的排序时间是一致的。

数据移动最少，即只需要n次交换。

时间复杂度 $O(n^2)$

空间复杂度 $O(1)$

1.2 插入排序

从索引1开始遍历数组，将当前的元素和左边的所有元素比较并放入合适的位置，直到索引到达最右端。

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
                int temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }

插入排序所需要的时间取决于输入元素的初始顺序，数组越有序，插入排序越快。

当数组中的倒置（数组中两个顺序颠倒的元素）的数量很少时，插入排序甚至可能比其他所有的排序算法都要快。

时间复杂度最好情况下（如有序数组） $O(n)$ 最坏情况下（如倒序数组） $O(n^2)$

空间复杂度 $O(1)$

2. 归并排序

将两个有序的数组归并成一个更大的有序数组。

可以自顶向下归并、自底向上归并。

原地归并两个已经排序好的数组的过程：

目的：将已排序好的 arr[lo ... mid]和已排序好的 arr[mid+1 ... hi]归并

将原数组 arr[lo ... hi] 复制到辅助数组 aux[lo ... hi] 中，两个指针分别从位置lo 和mid+1 开始往后走，比较两者的值，将较小的值依次放入arr[] 中

public static void merge(int[] arr, int lo, int mid, int hi) {
        int i = lo, j = mid+1;
        int[] aux = new int[arr.length];
        for (int k = lo; k <= hi; k++) {
            aux[k] = arr[k];
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid)              { arr[k] = aux[j++]; } 
            else if (j > hi)          { arr[k] = aux[i++]; } 
            else if (aux[j] < aux[i]) { arr[k] = aux[j++]; } 
            else                      { arr[k] = aux[i++]; }
        }
    }

自顶向下实现归并排序

private static void mergeSort(int[] arr, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = (hi - lo) / 2 + lo;
        mergeSort(arr, lo, mid);
        mergeSort(arr, mid+1, hi);
        merge(arr, lo, mid, hi);
    }

自底向上实现归并排序

private static void mergeFromBottom(int[] arr) {
        int N = arr.length;
        int[] aux = new int[N];
        for (int sz = 1; sz < N; sz = sz+sz) {
            for (int lo = 0; lo < N - sz; lo += sz+sz) {
                merge(arr, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
            }
        }
    }

时间复杂度 $O(nlogn)$

空间复杂度 $O(n)$ 即需要使用额外空间存储辅助数组

注：归并排序的代码在leetcode中可以通过，牛客网超时。

时间优化：

使用插入排序处理小规模的子数组（比如长度小于15）可以缩短运行时间，一般可节省10%~15%时间。
添加判断条件，如果arr[mid] <= arr[mid+1] 则说明两个数组不需要再归并了，可以跳过merge方法。

3. 快速排序

快速排序是一种分治的排序算法。它将找到一个元素把数组分成两个子数组，左边的所有元素不大于这个元素，右边的所有元素不小于这个元素，将两部分独立地排序。当两个子数组都有序时，整个数组也就自然有序了。

切分数组的策略：随意选定arr[lo]作为切分元素，从数组两端开始扫描数组，交换所有不满足“左侧元素不大于arr[lo]”和“右侧元素不小于arr[lo]”条件的元素。当两个指针相遇时，只需要将arr[lo]和左子数组最右侧元素arr[j] 交换之后返回 j 即可。

    private static void quickSort(int[] arr, int lo, int hi) {
        if (hi <= lo) { return; }
        int j = partition(arr, lo, hi);
        quickSort(arr, lo, j-1);
        quickSort(arr, j+1, hi);
    }

    private static int partition(int[] arr, int lo, int hi) {
        int i = lo, j = hi+1;
        int v = arr[lo];
        while (true) {
            while (arr[++i] < v) {
                if (i == hi) { break; }
            }
            while (v < arr[--j]) {
                if (j == lo) { break; }
            }
            if (i >= j) { break; }
            exchange(arr, i, j);
        }
        exchange(arr, lo, j);
        return j;
    }

4. 堆排序

二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆每个节点的左子树和右子树都是一个二叉堆。

当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。

二叉堆排序的思路：遍历未排序的数组，将数组中的每个数放入二叉堆中，再将堆顶元素弹出直至为空。

向二叉堆中添加元素：可将新的元素添加至最后一个叶子节点旁，与其父节点比较，逐渐上浮，即swim() 方法

弹出二叉堆堆顶元素：获得堆顶元素后，可将二叉堆最后一个叶子节点替换掉堆顶元素，将新的堆顶元素下沉至合适的位置，即sink() 方法。

用数组表示二叉堆：由于二叉堆是一个完全二叉树，因此可以采用层序遍历的方式将二叉堆存储在数组中，其中arr[0] 是堆顶元素，对于任意的arr[i]，其父节点为arr[(i-1)/2]，其左右子节点为 arr[2 * i + 1]，arr[2 * i + 2].

二叉堆深度为 $log(n)$