0%

快速排序

发表于 更新于 分类于

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

基本思想

快速排序递归的将子数组arr[left, right]排序，一般是取arr[left]作为切分元素，这个元素就是那个将要被排序的元素，然后调用partition()方法将arr[left]放到一个合适的位置，然后再递归重复上面的过程。所以该方法的关键在于切分。

切分方法partition()：

  1. 变量j记录最后一个小于arr[left]的元素的下标

  2. 让变量i从下标[left + 1, right]遍历数组元素

  3. 如果遍历过程中arr[i] < arr[left]，则j++，让arr[i]和arr[j]进行交换，如果arr[i] >= arr[left]，什么都不做继续遍历

  4. 最后把arr[left]和arr[j]进行一次交换

如图：

quick_sort.png

动态图如下(来源：https://www.cnblogs.com/onepixel/articles/7674659.html)：

quick_sort_2.png

代码实现

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
41
42
43
44
45
46
47
48

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author gelong
 * @date 2020/6/7 10:33
 */
public class QuickSort {

    public static <T> void sort(T[] data, Comparator<T> comparator) {
        sort(data, comparator, 0, data.length - 1);
    }

    private static <T> void sort(T[] data, Comparator<T> comparator, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(data, comparator, left, right);
        sort(data, comparator, left, p - 1);
        sort(data, comparator, p + 1, right);
    }

    private static <T> int partition(T[] data, Comparator<T> comparator, int left, int right) {
        int j = left;
        T v = data[left];
        for (int i = left + 1; i <= right; i++) {
            if (comparator.compare(data[i], v) < 0) {
                ++j;
                swap(data, i, j);
            }
        }
        swap(data, left, j);
        return j;
    }

    private static <T> void swap(T[] data, int i, int j) {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] data = {3, 1, 2, 5, 4};
        sort(data, Integer::compareTo);
        System.out.println(Arrays.toString(data));
    }
}

如果数组是近乎有序的情况下，上述快速排序就退化成了冒泡排序，时间复杂度为o(n^2)。因为我们每次取数组的第一个元素，如果数组是有序的情况下我们每次都会取到最小值，所以我们可以加入一个随机数，每次排序之前让第一个元素随机和其他位置的元素进行交换。这样会让每次取数组第一个元素但取到最小值的概率大大降低，近乎为0。

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
41
42
43
44
45
46
47
48
49
50
51
52

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

/**
 * @author gelong
 * @date 2020/6/7 10:33
 */
public class QuickSort {

    private static Random random = new Random();

    public static <T> void sort(T[] data, Comparator<T> comparator) {
        sort(data, comparator, 0, data.length - 1);
    }

    private static <T> void sort(T[] data, Comparator<T> comparator, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(data, comparator, left, right);
        sort(data, comparator, left, p - 1);
        sort(data, comparator, p + 1, right);
    }

    private static <T> int partition(T[] data, Comparator<T> comparator, int left, int right) {
        swap(data, left, random.nextInt(right - left + 1) + left);
        int j = left;
        T v = data[left];
        for (int i = left + 1; i <= right; i++) {
            if (comparator.compare(data[i], v) < 0) {
                ++j;
                swap(data, i, j);
            }
        }
        swap(data, left, j);
        return j;
    }

    private static <T> void swap(T[] data, int i, int j) {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] data = {3, 1, 2, 5, 4};
        sort(data, Integer::compareTo);
        System.out.println(Arrays.toString(data));
    }
}

上述代码还是存在缺陷，当数组中重复元素非常多的时候，等于v的元素太多，那么就将数组分成了极度不平衡的两个部分，因为等于v的部分总是集中在数组的某一边，此时快速排序将会变得非常慢。那么一种优化的方式便是进行双路快排。

和普通快排不同的是此时我们将小于v和大于v的元素放在数组的两端，那么我们将引用新的索引j的记录大于v的边界位置。如图：

quick_sort_3.png

i不断往后扫描直到遇到>=v的元素，j也不断往前扫描直到遇到<=v的元素，如图：

quick_sort_4.png

此时我们交换i和j的元素即可，然后继续遍历直到i>=j。

quick_sort_5.png

最后把arr[left]和arr[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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

/**
 * @author gelong
 * @date 2020/6/7 10:33
 */
public class QuickSort2 {

    private static Random random = new Random();

    public static <T> void sort(T[] data, Comparator<T> comparator) {
        sort(data, comparator, 0, data.length - 1);
    }

    private static <T> void sort(T[] data, Comparator<T> comparator, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(data, comparator, left, right);
        sort(data, comparator, left, p - 1);
        sort(data, comparator, p + 1, right);
    }

    private static <T> int partition(T[] data, Comparator<T> comparator, int left, int right) {
        swap(data, left, random.nextInt(right - left + 1) + left);
        int i = left + 1;
        int j = right;
        T v = data[left];
        while (true) {
            while (i <= right && comparator.compare(data[i], v) < 0) {
                i++;
            }
            while (j >= left + 1 && comparator.compare(data[j], v) > 0) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(data, i, j);
            i++;
            j--;
        }
        swap(data, left, j);
        return j;
    }

    private static <T> void swap(T[] data, int i, int j) {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] data = {3, 1, 2, 5, 4};
        sort(data, Integer::compareTo);
        System.out.println(Arrays.toString(data));
    }
}

除了双路快排之外，还有一个更加经典的优化，我们叫它三路快排。

双路快排将整个数组分成了<v，>v的两部分，而三路快排则是将数组分成了<v，==v，>v的三个部分，当递归处理的时候，遇到==v的元素直接不用管，只需要处理<v，>v的元素就好了。如图：

quick_sort_5.png

i不断往后遍历，当元素e < v时，我们就让lt + 1和i进行一次交换，然后i++，如图：

quick_sort_6.png

当元素e > v时，我们我们就让gt-1和i进行一次交换，继续比较i和v的值，如图：

quick_sort_7.png

当i == gt时，全部元素就处理完了，如图：

quick_sort_8.png

最后我们交换lt和left的元素即可。

三路快排的代码如下：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

/**
 * @author gelong
 * @date 2020/6/7 10:33
 */
public class QuickSort3 {

    private static Random random = new Random();

    public static <T> void sort(T[] data, Comparator<T> comparator) {
        sort(data, comparator, 0, data.length - 1);
    }

    private static <T> void sort(T[] data, Comparator<T> comparator, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(data, comparator, left, right);
        sort(data, comparator, left, p - 1);
        sort(data, comparator, p + 1, right);
    }

    private static <T> int partition(T[] data, Comparator<T> comparator, int left, int right) {
        swap(data, left, random.nextInt(right - left + 1) + left);
       	// [left + 1, lt] < v
       	int lt = left;
       	// [gt, right] > v
       	int gt = right + 1;
       	// [lt + 1, i) == v
       	int i = left + 1;
        T v = data[left];
        while (i < gt) {
            if (comparator.compare(data[i], v) < 0) {
                swap(data, i, lt + 1);
                lt++;
                i++;
            } else if (comparator.compare(data[i], v) > 0) {
                swap(data, i, gt - 1);
                gt--;
            } else {
                i++;
            }
        }
        swap(data, left, lt);
        return lt;
    }

    private static <T> void swap(T[] data, int i, int j) {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] data = {3, 1, 2, 5, 4};
        sort(data, Integer::compareTo);
        System.out.println(Arrays.toString(data));
    }
}