归并排序 - 分治

时间复杂度 O(NlogN)

java 代码

import java.io.*; // 输入输出

class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int[] q = new int[n];
        args = br.readLine().split(" ");
        for (int i = 0; i < n; ++i) {
            q[i] = Integer.valueOf(args[i]);
        }
        //quick_sort(q, 0, n - 1);
        tmp = new int[n];
        merge_sort(q, 0, n - 1);
        System.out.print(q[0]);
        for (int i = 1; i < n; ++i) {
            System.out.print(" " + q[i]);
        }
    }
    static int[] tmp; // 归并排序辅助数组
    public static void merge_sort(int[] q, int l, int r) {
        // 递归边界条件
        if (l >= r) return;
        // 求中间下标
        int mid = (l + r) / 2;
        // 归并排序两边
        merge_sort(q, l, mid); merge_sort(q, mid + 1, r);

        // 合并排序好的两边
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (q[i] <= q[j]) tmp[k++] = q[i++];
            else tmp[k++] = q[j++];
        }
        while (i <= mid) {
            tmp[k++] = q[i++];
        }
        while (j <= r) {
            tmp[k++] = q[j++];
        }
        // 这里合并需要 i 从 l开始  而 j是从0开始 
        for (i = l, j = 0; i <= r; ++i, ++j) {
            q[i] = tmp[j];
        }
    }

    public static void quick_sort(int[] q, int l, int r) {
        // 判断递归边界
        if (l >= r) return;
        // 枢纽为中间值
        int x = q[(l + r + 1) / 2], i = l - 1, j = r + 1;

        while (i < j) {
            do ++i; while (q[i] < x); // 跳过那些小于x的
            do --j; while (q[j] > x); // 跳过那些大于x的
            // 交换
            if (i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }
        quick_sort(q, l, i - 1); // 需要注意的是这里 用 j 上面 x就不能是右边界,反之 用i就不能是左边界
        quick_sort(q, i, r);
        /*
            int x = q[(l + r) / 2], i = l - 1, j = r + 1;
            quick_sort(q, l, j); // 需要注意的是这里 用 j 上面 x就不能是右边界,反之 用i就不能是左边界
            quick_sort(q, j + 1, r);
        */
    }
}