464. 整数排序 II（排序算法）

问题

给一组整数，请将其在原地按照升序排序。使用归并排序，快速排序，堆排序或者任何其他 O(n log n) 的排序算法。

样例
例1：

输入：[3,2,1,4,5]，
输出：[1,2,3,4,5]。
例2：

输入：[2,3,1]，
输出：[1,2,3]。

快速排序

平均运行时间为O(NlogN)，最坏的运行时间为O(N^2)
一句话总结，就是通过交换实现关键字左边的元素不大于关键字，关键字右边的元素不小于关键字。
快速排序利用了分治的策略。而分治的基本基本思想是：将原问题划分为若干与原问题类似子问题，解决这些子问题，将子问题的解组成原问题的解。
那么如何利用分治的思想对数据进行排序呢？假如有一个元素集合A：

• 选择A中的任意一个元素pivot，该元素作为基准
• 将小于基准的元素移到左边，大于基准的元素移到右边（分区操作）
• A被pivot分为两部分，继续对剩下的两部分做同样的处理
  直到所有子集元素不再需要进行上述步骤

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */

    public void sortIntegers2(int[] A) {
        // write your code here
        //快速排序
        quickSort(A, 0, A.length - 1);

    }

    private void quickSort(int[] arr, int start, int end) {
        if (start >= end)
            return;
        int left = start;
        int right = end;
        int pivot = arr[start];
        while (left <= right) {
            while (pivot < arr[right] && left <= right) {
                right--;
            }
            while (pivot > arr[left] && left <= right) {
                left++;
            }
            // 将小于关键字和大于关键字的元素交换位置
            if (left <= right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }

        // 以关键字为界限将待排序元素划分成 两个区域分别进行快速排序
        quickSort(arr, start, right);
        quickSort(arr, left, end);
    }

    private void swap(int a[], int m, int n) {
        int tmp = a[m];
        a[m] = a[n];
        a[n] = tmp;
    }

}

归并排序

https://www.cnblogs.com/chengxiao/p/6194356.html

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
    public void sortIntegers2(int[] A) {
        // write your code here
        if (A == null || A.length == 0)
            return;

        // 放在外面new会比较好，这样只需要new一次，不用次次进函数new
        int[] temp = new int[A.length];
        mergeSort(A, 0, A.length - 1, temp);
    }

    private void mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end)
            return;

        // 无脑分治
        int mid = start + (end - start) / 2;
        mergeSort(A, start, mid, temp);
        mergeSort(A, mid + 1, end, temp);

        // 合并
        merge(A, start, end, temp);
    }

    private void merge(int[] A, int start, int end, int[] temp) {
        // 左右两半边数组的起始index
        int mid = start + (end - start) / 2;
        int leftIndex = start;
        int rightIndex = mid + 1;

        int index = leftIndex; // temp数组的下标

        while (leftIndex <= mid && rightIndex <= end) {
            if (A[leftIndex] < A[rightIndex])
                temp[index++] = A[leftIndex++];
            else
                temp[index++] = A[rightIndex++];
        }

        // 若是有数组还未结束，手动将之加入
        while (leftIndex <= mid)
            temp[index++] = A[leftIndex++];

        while (rightIndex <= end)
            temp[index++] = A[rightIndex++];

        // 将temp中的数字放回原数组组中
        for (int i = start; i <= end; i++)
            A[i] = temp[i];
    }
}