快速排序使用分治思想,实际实现过程和二叉树的前序遍历很像,在第一次碰到节点时进行遍历分区,然后再对子分区进行遍历分区,直到分区中只有一个节点或是没有节点为止。

  • 时间复杂度为:O(logn)
  • 空间复杂度为: O(1)

以下是代码实现

 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
64
65
66
67
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {6, 4, 3, 2, 7, 9, 1, 8, 5};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] array) {
        internalQuickSort(array, 0, array.length - 1);
    }

    private static void internalQuickSort(int[] array, int left, int right) {
        if (left >= right)
            // 当 left == right 时,表示需要排序的数组只有一个数字 right - left + 1 = 1
            // 这种情况说明 mid 排序后在倒数第二个元素
            // 当 left > right 时,其实 left = right + 1,那么表示没有需要要排序的数字
            // right - left + 1 = 0,这种情况说明 mid 排序后在最后一个元素
            return;
        int pivot = partition(array, left, right);
        // pivot - 1 区间范围缩小到中心点的左边,不包含中心点
        internalQuickSort(array, left, pivot - 1);
        // pivot + 1 区间范围缩小到中心点的右边,不包含中心点
        internalQuickSort(array, pivot + 1, right);
    }

    // 从小到大遍历
    private static int partition(int[] array, int left, int right) {
        // 这里选定最右边的点作为中心点
        // 这里由于将最右边的点作为了分区点,并用 pivot 保存了起来
        // 所以这个 pivot 数组上的位置便可以被替换掉了
        int pivot = array[right];
        // 我们使用左右指针,先从左边开始遍历
        int leftIndex = left;
        int rightIndex = right;
        // 当左指针跑到右指针的右边时停止循环
        while (leftIndex < rightIndex) {
            if (array[leftIndex] <= pivot) {
                // 先遍历左边,只要左边的数字比 pivot 小,就不动,指将指针加一就进行
                // 下一次循环,如果出现左边的数字比 pivot 大,则停止循环
                leftIndex++;
            } else {
                // 左边的数字比 pivot 大,将左边的数字移动到右边
                // 空位跑到 leftIndex 所指的位置
                // 接下来从右边开始遍历
                array[rightIndex--] = array[leftIndex];
                // 停止循环
                break;
            }
        }
        while (leftIndex < rightIndex) {
            if (array[rightIndex] >= pivot) {
                // 然后遍历右边,只要右边的数字比 pivot 大,就不动,将指针减一就进行下一次循环
                // 如果出现右边的数字比 pivot 小,则停止循环
                rightIndex--;
            } else {
                // 右边的数字比 pivot 小,那么就将该数字移动到左边
                array[leftIndex++] = array[rightIndex];
                // 停止循环
                break;
            }
        }
        // 遍历结束后到这里 rightIndex 是等于 leftIndex 的
        // 这个位置便是存放 pivot 的
        array[leftIndex] = pivot;
        return leftIndex;
    }
}

下图是上述代码遍历时 left 和 right 的变化过程

分区路径

参考资料

  1. 面试 12:玩转 Java 快速排序