目录

快速排序( Quick Sort )的实现

2017-12-01 约 413 字预计阅读 1 分钟

目录

快速的排序逻辑

快速排序的主要思想是递归

第一步：对需要排序的所有元素进行Shuffle。
第二步：取第一个元素为区分元素k，取第二个元素为i，取最后一个元素为j，i向右j向左分别迭代，最后替换k元素和j元素，最终保持k左侧的元素都小于k，右侧元素都大于k。
第三步：不停对左右部分再次进行上一步动作，最终排序完成。

Java代码实现

 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


public class QuickSort {

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

private 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);
}

private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo, j = hi + 1;
    while (true) {
        while (less(a[++i], a[lo])) {
            if (i == hi) {
                break;
            }
        }
        while (less(a[lo], a[--j])) {
            if (j == lo) {
                break;
            }
        }
        if (i >= j) {
            break;
        }
        swap(a, i, j);
    }
    swap(a, lo, j);
    return j;
}

}

小优化

在数组大小较小时，使用插入排序比快速排序执行效率要高。

1

private static final int INSERTIONSORT_THRESHOLD = 7;

1
2
3


if ((hi - lo) < INSERTIONSORT_THRESHOLD) {
	InsertionSort.sort(a, lo, hi);
}

以上，快速排序的思想真的有些烧脑，实现起来坑还是很多，需要仔细仔细再仔细的思考每一个细节。