每一秒钟的时间都值得铭记

0%

排序算法之快速排序

发表于 分类于
本文字数： 5.3k 阅读时长 ≈ 5 分钟

什么是快速排序

和冒泡排序一样，快速排序也属于交换排序，通过元素直接的比较和交换位置来达到排序的目的。

快速排序的思想是：在每一轮挑选一个基准元素，并让其他比它大的元素移动到数的一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。

这种思想就叫做分治法。

基准元素的选择

基准元素（pivot），在分治过程中，以基准元素为中心，要把其他元素移动到它的左右两边。

那么如何选择基准元素呢？

选择数组的第一个元素

这种方法是最简单，而且在绝大多数的情况都不会出现问题。但是如果有一个逆序的数列，期望排成顺序的数列，使用快速排序的时候，会出现一种最坏的情况。

由于这个数组原本是逆序的，在选择基准元素之后，由于确定的基准元素都是在数组的边界位置，永远都是比其他元素大，或者比其他元素小，这样一来，快速排序就会退化为一种 O(n^2) 级别的排序。

随机选择一个元素

为了解决上述情况可能出现的最坏情况，可以使用随机选择一个数组元素最为基准元素，并让选中的基准元素和数组的第一个元素进行位置交换即可。

当然，随机选择一个元素的方法可以尽量避免快速排序出现最坏的情况，但是仍然有可能会出现极端的情况。

所以快速排序的平均时间复杂度为 O(nlogn)，但最坏情况下的时间复杂度为 O(n^2)。

算法实现

选中基准元素之后，就可以进行数组的元素交换操作了，就是将比基准元素小的元素放在基准元素左边，比基准元素大的元素放在基准元素右边。

双边循坏法

1、选中基准元素（pivot），并将排序的数组最左边和最右边的元素索引设为 left 和 right。

2、从 right 指针开始向左索引，如果指针指向的元素大于等于基准元素，则继续向左边移动，如果元素比基准元素小，则 right 指针停止移动。

3、从 left 指针开始向右索引，如果指针指向的元素小于等于基准元素，则继续向右边移动，如果元素比基准元素大，则 left 指针停止移动。

4、交换 left 和 right 索引位置的元素。

5、从之前停止的 left 和 right 指针的位置，继续重复 2、3 步骤，直到 left 指针等于 right 指针，停止索引。

6、交换 left 和 pivot 指针的元素。

7、根据基准元素的位置，将数组一分为二，并继续从第一步开始执行，直到所有元素有序。

  • 代码实现
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
public static void main(String[] args) {
    SortRunner.run(SortUtils.generateRandomArray(10000, 100, 100000),
            (arr) -> {
                quickSort(arr, 0, arr.length - 1);
            });
}


private static void quickSort(int[] arr, int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    int pivotIndex = partition(arr, startIndex, endIndex);
    // 7、根据基准元素的位置，将数组一分为二，并继续从第一步开始执行，直到所有元素有序。
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);

}

private static int partition(int[] arr, int startIndex, int endIndex) {
    // 1、选中基准元素（pivot），并将排序的数组最左边和最右边的元素索引设为 left 和 right。
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;
    // 5、从之前停止的 left 和 right 指针的位置，继续重复 2、3 步骤，直到 left 指针等于 right 指针，停止索引。
    while (left != right) {
        // 2、从 right 指针开始向左索引，如果指针指向的元素大于等于基准元素，则继续向左边移动，如果元素比基准元素小，则 right 指针停止移动。
        while (left < right && arr[right] > pivot) {
            right--;
        }
        // 3、从 left 指针开始向右索引，如果指针指向的元素小于等于基准元素，则继续向右边移动，如果元素比基准元素大，则 left 指针停止移动。
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        //  4、交换 left 和 right 索引位置的元素。
        if (left < right) {
            SortUtils.swap(arr, left, right);
        }
    }
    // 6、交换 left 和 pivot 指针的元素。
    SortUtils.swap(arr, startIndex, left);
    return left;
}

单边循环法

1、选中基准元素（pivot），并将数组的第一个元素索引设为 mark，mark 指针代表小于基准元素的边界。

2、从基准元素的下一个位置开始遍历数组，如果遍历到的元素大于基准元素，则继续向后遍历。

3、如果遍历到的元素小于基准元素，将 mark 指针的位置向后移动一位，并交换 mark 指针指向的元素和当前遍历到的元素的位置。

4、遍历结束后，交换 pivot 和 mark 指针的位置。

5、根据基准元素的位置，将数组一分为二，并继续从第一步开始执行，直到所有元素有序。

  • 代码实现
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
public static void main(String[] args) {
    SortRunner.run(SortUtils.generateRandomArray(10000, 100, 100000),
            (arr) -> {
                quickSort(arr, 0, arr.length - 1);
            });
}


private static void quickSort(int[] arr, int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    int pivotIndex = partition(arr, startIndex, endIndex);
    // 5、根据基准元素的位置，将数组一分为二，并继续从第一步开始执行，直到所有元素有序。
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
}

private static int partition(int[] arr, int startIndex, int endIndex) {
    // 1、选中基准元素（pivot），并将数组的第一个元素索引设为 mark，mark 指针代表小于基准元素的边界。
    int pivot = arr[startIndex];
    int mark = startIndex;
    // 2、从基准元素的下一个位置开始遍历数组，如果遍历到的元素大于基准元素，则继续向后遍历。
    for (int i = startIndex + 1; i <= endIndex; i++) {
        // 3、如果遍历到的元素小于基准元素，将 mark 指针的位置向后移动一位，并交换 mark 指针指向的元素和当前遍历到的元素的位置。
        if (arr[i] < pivot) {
            mark++;
            SortUtils.swap(arr, mark, i);
        }
    }
    // 4、遍历结束后，交换 pivot 和 mark 指针的位置。
    SortUtils.swap(arr, startIndex, mark);
    return mark;
}

非递归实现

递归的本质就是一个方法通过不同参数调用自身，在 Java 虚拟机的表现本质上就是将方法进行压栈，执行完成之后进行出栈操作。

所以快速排序的非递归实现可以使用一个栈来进行代替。

1、创建一个栈，将数组的开始索引和结束索引压入栈中。

2、取出栈顶的元素，通过数组的开始索引和结束索引，对该范围内的数组元素进行排序，获取基准元素。

3、根据基准元素的位置，将数组一分为二，并将切分的数组的开始索引和结束索引压入栈中。

4、轮询栈，只要栈内元素不为空，继续执行，否则停止程序。

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
public static void main(String[] args) {
    SortRunner.run(SortUtils.generateRandomArray(10000, 100, 100000),
            (arr) -> {
                quickSort(arr, 0, arr.length - 1);
            });
}

private static void quickSort(int[] arr, int startIndex, int endIndex) {
    // 1、创建一个栈，将数组的开始索引和结束索引压入栈中。
    Stack<Map<String, Integer>> stack = new Stack<>();
    Map<String, Integer> map = new HashMap<>();
    map.put("start", startIndex);
    map.put("end", endIndex);
    stack.push(map);
    // 4、轮询栈，只要栈内元素不为空，继续执行，否则停止程序。
    while (!stack.isEmpty()) {
        // 2、取出栈顶的元素，通过数组的开始索引和结束索引，对该范围内的数组元素进行排序，获取基准元素。
        Map<String, Integer> pop = stack.pop();
        int start = pop.get("start");
        int end = pop.get("end");
        int pivotIndex = partition(arr, start, end);
        // 3、根据基准元素的位置，将数组一分为二，并将切分的数组的开始索引和结束索引压入栈中。
        if (start < pivotIndex - 1) {
            Map<String, Integer> leftParam = new HashMap<>();
            leftParam.put("start", start);
            leftParam.put("end", pivotIndex - 1);
            stack.push(leftParam);
        }
        if (end > pivotIndex + 1) {
            Map<String, Integer> rightParam = new HashMap<>();
            rightParam.put("start", pivotIndex + 1);
            rightParam.put("end", end);
            stack.push(rightParam);
        }
    }
}

private static int partition(int[] arr, int startIndex, int endIndex) {
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;
    while (left != right) {
        while (left < right && arr[right] > pivot) {
            right--;
        }
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        if (left < right) {
            SortUtils.swap(arr, left, right);
        }
    }
    SortUtils.swap(arr, startIndex, left);
    return left;
}

最后

本文Github https://github.com/herenpeng/code-learn 已收录，欢迎Star。

坚持原创技术分享，您的支持将鼓励我继续创作！
-------------这是我的底线^_^-------------