题解 | #排序#

解题思路

题目要求解题时间在1s内，那么就限定了排序算法范围在快排、堆排和归并排序之间，下面依次实现之；

快排

算法原理

快排采用了分治的思想：要对数组A进行排序，可以先将A分成两个子数组A1和A2，并同时保证A1中任一元素值小于A2中任一元素，然后对两子数组在重复此操作直到数组无法再进行分割，最后将各个子数组拼接起来便是一个有序数组了。用算法表述如下：

quickSort(A, p, r) {
    if (p < r) {
        q = partition(A, p, r);
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
    }
}

其中最关键的就是partion()方法了，它负责将一个数组A分成两个子数组A[p..q-1]和A[q+1..r]，结果是A[p..q-1]中任一数值小于A[q+1..r]中任一数值，两子数组分界点便是A[q]；借用《算法导论》中图示如下：

在partition()处理过程中将存在如下三个区：

算法实现

public class Solution {
    public int[] MySort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    private void quickSort(int[] A, int p, int r) {
        if (p < r) {
            int q = partition(A, p, r);
            quickSort(A, p, q - 1);
            quickSort(A, q + 1, r);
        }
    }

    private int partition(int[] A, int p, int r) {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j < r; j++) {
            if (A[j] <= x) {
                swap(A, ++i, j);
            }
        }
        swap(A, i + 1, r);
        return i + 1;
    }

    private void swap(int[] arr, int i, int j) {
        if (arr[i] != arr[j]) {
            arr[i] ^= arr[j];
            arr[j] ^= arr[i];
            arr[i] ^= arr[j];
        }
    }
}

归并排序

算法原理

与快排一样，归并排序同样利用分治思想：它先对数组A进行二分，直到不能分割为止，最后将得到各单调子数组（每个数组只包含一个数值，因此必然是单调的），最后将各单调子数组合起来即为排序后数组，用算法描述如下：

mergeSort(A, p, r) {
    if (p < r) {
        q = p + ((r - q) >> 1);
        mergeSort(A, p, q);
        mergeSort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

再次借用《算法导论》图示进行说明：

对于数组A[p,r]=[5,2,4,7,1,3,2,6]，先将其进行二分，得到各单调子数组，也即最下面那行；然后通过归并操作(merge())不停的将两个单调数组合为一个，最终得到一个有序数组；
我们不难发现，最重要的就是merge()操作：它用来将两个单调数组（A[p..q]和A[q..r]）合为一个单调数组A'[p..r]；处理起来也很简单，只要新开辟一个数组与归并后数组大小一样，然后逐个比较两个单调数组，按比较的值从小到大放到新开辟数组中；

算法实现

public class Solution {
    public int[] MySort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
        return arr;
    }

    private void mergeSort(int[] A, int L, int R) {
        if (L < R) {
            int M = L + ((R - L) >> 1);
            mergeSort(A, L, M);
            mergeSort(A, M + 1, R);
            merge(A, L, M, R);
        }
    }

    // 合并两单调数组(A[L..M]和A[M+1..R])为一个单调数组
    private void merge(int[] A, int L, int M, int R) {
        int[] tmp = new int[R - L + 1];
        int index = 0;
        int i = L, j = M + 1;
        while (i <= M && j <= R) {
            if (A[i] <= A[j]) {
                tmp[index++] = A[i++];
            } else {
                tmp[index++] = A[j++];
            }
        }
        while (i <= M) {
            tmp[index++] = A[i++];
        }
        while (j <= R) {
            tmp[index++] = A[j++];
        }

        for (int k = 0; k < tmp.length; k++) {
            A[L + k] = tmp[k];
        }
    }
}