排序算法--快速排序

发表于 分类于

快速排序

快速排序是排序算法中使用最广泛的算法了，之所以使用如此广泛，是因为其适用于各种不同的输入数据并且比其他的一般排序算法要快很多。

思想

快速排序是一种分治的排序算法。它将一个数组分成两个子数组。将两部分独立排序。当两个子数组都有序时，整个数组也就有序了。快速排序对数组切分的位置取决于数组的内容。

实现上述思路可以使用递归思想，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class QuickSort{

    public static void sort(Comparable[] a){
        sort(a, 0, a.length - 1);
    }

    public static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        int j = partition(a, lo, hi); //切分算法
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    public static int partition(Comparable[] a, int lo, int hi){
        //待实现
        return 0;
    }
}

切分策略

先随意取出a[lo]作为切分元素，即将会被排定的元素，然后从数组的最左端开始向右扫描【左指针i】，直到找到一个大于等于它的元素a[i]，再从数组的最右端开始向左扫描【右指针j】，直到找到一个小于等于它的元素a[j]，交换[ai]和a[j]的位置，如此继续，如此便可以保证左侧指针i的左边元素都比切分元素小，而右指针j的右侧的元素都不小于切分元素。当两个指针相遇时，只需将切分元素a[lo]和左子数组的最右侧元素交换a[j]即可。实现如下：

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
public static int partition(Comparable[] a, int lo, int hi) {
    //定义左指针i，右指针j
    int i = lo, j = hi + 1;
    Comparable v = a[lo];
    //循环移动指针
    while (true) {
        //从左向右扫描
        while (a[++i].compareTo(v) < 0) {
            if (i == hi)
                break;
        }
        //从右向左扫描
        while (v.compareTo(a[--j]) < 0) {
            if (j == lo)
                break;
        }
        //两个指针相遇时，终止循环
        if (i >= j)
            break;
        //交换指针i和指针j位置上的元素
        exchange(a, i, j);

    }
    //最后交换a[lo]和左子数组中的最右边的元素（此时i == j）
    exchange(a, lo, j);
    return j;
}

public static void exchange(Comparable[] a, int i, int j){
    Comparable temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}