SortAlgosKt(5) - 快速排序

算法思想

快速排序和归并排序一样，也是应用了分治的思想。

算法分为三步：

在待排序数组中，选择一个元素作为"基准"（pivot），一般是数组第一个元素。
遍历数组，所有小于 pivot 的元素都移到 pivot 左边；所有大于 pivot 的元素移到 pivot 的右边。
对 pivot 左右两边的数组重复步骤1和步骤2，直到只剩下一个元素为止。

关键在于第二步这个分区（partition）的过程如何实现。可以对当前数组进行遍历，并用一个变量标记分割点的位置，分割点表示左边的数都比 pivot 小，右边的都比 pivot 大，遇到比 pivot 小的数就把标记位置右移一位，然后交换标记位置的元素和当前遍历到的元素。遍历结束后，再把 pivot 元素和标记位置的元素进行交换，这次 partition 就算结束了。

partition 的过程可以参考下面这个《算法导论》里的图进行理解，只不过这个图是把数组的最后一个数作为 pivot 元素，原理是一样的。我更喜欢直接用第一个元素作为 pivot ，后面实现代码里的 partition 方法也是按照第一个元素来实现的。

算法实现

 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
fun quickSort(nums: IntArray) {
    if (nums.size < 2) return
    quickSortImpl(nums, 0, nums.lastIndex)
}

fun quickSortImpl(nums: IntArray, l: Int, r: Int) {
    if (l < r) {
        val partition = partition(nums, l, r)
        quickSortImpl(nums, l, partition)
        quickSortImpl(nums, partition + 1, r)
    }
}

fun partition(nums: IntArray, l: Int, r: Int): Int {
    val pivot = nums[l]
    var i = l
    for (j in l..r) {
        if (pivot > nums[j]) {
            i++
            swap(nums, i, j)
        }
    }
    swap(nums, l, i)
    return i
}

拓展 - 随机快速排序

有这么一种情况，待排序数组如果已经有序，那么上面的快速排序方法就会显得效率很低。因为每次把第一个元素作为 pivot 进行 partition 后，总有一个序列是不含任何元素的，此时时间复杂度到达了O(n^2)。这种情况下我们可以使用随机快速排序，也就是每次进行 partition 操作的时候，随机选一个元素作为 pivot ，这样可以实现无论输入数组是否有序，排序时的分区总是相对均衡的。

新增加一个 randPartition 方法用来实现随机快排,

1
2
3
4
5
fun randPartition(nums: IntArray, l: Int, r: Int): Int {
    val randIndex = Random.nextInt(l, r + 1)
    swap(nums, randIndex, l)
    return partition(nums, l, r)
}

然后修改原来调用 partition 方法为调用 randPartition 方法。

1
2
3
4
5
6
7
fun quickSortImpl(nums: IntArray, l: Int, r: Int) {
    if (l < r) {
        val partition = randPartition(nums, l, r)
        quickSortImpl(nums, l, partition)
        quickSortImpl(nums, partition + 1, r)
    }
}

文章目录

算法思想

算法实现

拓展 - 随机快速排序