基础算法 - 分治

(快排)

时间复杂度

O(Nlog(N))

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);
        System.out.print(q[0]);
        for (int i = 1; i < n; ++i) {
            System.out.print(" " + q[i]);
        }
    }
    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);
        */
    }
}