快速排序（Java）

快速排序的特点是：递归，原地排序。
时间复杂度平均和最好情况为O（nlgn）、最差情况为O（n^2）。
空间复杂度为O(lgn)
它也是不稳定的
代码如下：

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        double[] A = new double[10];
        for(int i = 0; i < A.length; i++)
            A[i] = (int)(Math.random()*100);//为了结果看起来简洁点，这里就强转成int

        quickSort(A, 0, A.length - 1);//注意传的是数组的下标范围

        System.out.println(Arrays.toString(A));
    }

    public static int partition(double[] A, int p, int r) {
        double divide = A[r];
        int i = p - 1;//i在循环中永远是最新发现的比分界小的数的下标,初始别写成-1了
        for(int j = p; j <= r - 1; j++) {//注意是r-1，r作为分界了
            if(A[j] <= divide) {
                double e = A[++i];
                A[i] = A[j];
                A[j] = e;
            }
        }
        A[r] = A[++i];
        A[i] = divide;
        return i;//返回分界处数字的下标
    }

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

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

初学者一只，欢迎大家指正错误。