快速排序的几种实现方式

快速排序(quick sort)的特点是分块排序,也叫划分交换排序(partition-exchange sort)

代码实现方式可以有这么几种:

  1. 拼接结果
  2. 左右相互交换
  3. 快慢指针

1. 拼接结果

# Python3
class Solution:
    def quicksort(self, nums):
        # 当为 0 个或 1 个时,肯定有序,直接返回
        if len(nums) < 2:
            return nums
        else:
            # 选择第一位作为中位数
            mid = nums[0]
            less = [num for num in nums[1:] if num <= mid]
            greater = [num for num in nums[1:] if num > mid]
            return self.quicksort(less) + [mid] + self.quicksort(greater)

这种方式最直观,最好理解,但效率不高。为了找出大于和小于中位数的元素,循环遍历了 2 次

做一点小小的修改,改为一次遍历:

class Solution:
    def quicksort(self, nums):
        if len(nums) < 2:
            return nums
        else:
            mid = nums[0]
            less, greater = self.partition(nums, mid)[0], self.partition(nums, mid)[1]
            return self.quicksort(less) + [mid] + self.quicksort(greater)

    def partition(self, nums, mid):
        less, greater = [], []
        for num in nums[1:]:
            if num <= mid:
                less.append(num)
            else:
                greater.append(num)
        return less, greater

优化后,运行时间降低了,但空间使用还很高,每次递归都额外需要 2 个平均长度为 ¼ n 的数组

1 + 2 ... + n-1 + n = ((1 + n) * n ) / 2
平均值 = ((1 + n) * n ) / 2 / n = (1 + n) / 2
两个数组平分平均值: (1 + n) / 2 / 2 ≈ 1/4 n

2. 左右相互交换

其实可以不使用额外空间,直接操作原数组。选择一个基准值,将小于它和大于它的元素相互交换。

class Solution:
    def quicksort(self, nums):
        self.quick_sort(nums, 0, len(nums) - 1)

    def quick_sort(self, nums, start, end):
        # end - start < 1
        if start >= end:
            return
        
        # 每次使用最后一个数作为基准值
        pivot_index = end
        pivot = nums[pivot_index]
        
        left, right = start, end - 1

        while left < right:
            # 左边跳过所有小于基准值的元素
            while nums[left] <= pivot and left < right:
                left += 1
            # 右边跳过所有大于基准值的元素
            while nums[right] > pivot and left < right:
                right -= 1

            # 交换
            nums[left], nums[right] = nums[right], nums[left]

        # 此时左右指针重合(left == right),其指向元素可能大于基准值
        if nums[left] > pivot:
            nums[left], nums[pivot_index] = nums[pivot_index], nums[left]
        # 使 left 始终作为较大区间的第 1 个元素
        else:
            left += 1
            
        self.quick_sort(nums, start, left - 1)
        # pivot 不一定在中间,所以包含 left
        self.quick_sort(nums, left, end)

使用此种方式,最好要将开头或末尾的元素设为基准值。如果使用中间元素,也需要交换到末尾

排序过程:

[6  5  3  1  8  7  2  4]
 ↑                 ↑  ^
[2  5  3  1  8  7  6  4]
    ↑     ↑           ^
[2  1  3  5  8  7  6  4]
          ↑↑          ^
[2  1  3  4  8  7  6  5]
          ^           
[2  1  3][4  8  7  6  5]

nums[left] <= pivot 时:

[6  7  3  4  8  1  2  5]
 ↑                 ↑  ^
[2  7  3  1  8  1  6  5]
    ↑           ↑     ^
[2  1  3  4  8  7  6  5]
          ↑↑          ^
[2  1  3  4][8  7  6  5]

3. 快慢指针

上面这种方式其实使用两个相向指针,也可以使用同向快慢指针实现元素交换。

class Solution:
    def quicksort(self, nums):
        import random
        
        def quick_sort(left, right):
            # right - left < 1
            if left >= right:
                return

            # 随机选择一个元素作为 pivot
            pivot_index = random.randint(left, right)
            pivot = nums[pivot_index]

            # 1. 将中位数与末尾数交换,便于操作
            nums[pivot_index], nums[right] = nums[right], nums[pivot_index]

            # 2. 使用快慢指针,将所有小于中位数的元素移动到左边
            store_index = left
            for i in range(left, right):
                if nums[i] <= pivot:
                    nums[store_index], nums[i] = nums[i], nums[store_index]
                    store_index += 1

            # 3. store_index 位置元素肯定大于等于 pivot,所以交换
            nums[right], nums[store_index] = nums[store_index], nums[right]

            # 因为 pivot 在中间,所以减 1
            quick_sort(left, store_index - 1)
            # 因为 pivot 在中间,所以加 1
            quick_sort(store_index + 1, right)

        quick_sort(0, len(nums) - 1)

排序过程:

[6  5  3  1  8  7  2  4]
 ↑↑                   ^
[6  5  3  1  8  7  2  4]
 ↑     ↑              ^
[3  5  6  1  8  7  2  4]
    ↑     ↑           ^
[3  1  6  5  8  7  2  4]
       ↑           ↑  ^
[3  1  2  5  8  7  6  4]
          ↑           ^
[3  1  2  4  8  7  6  5]
          ^     
[3  1  2][4][8  7  6  5]

随机选择可以增加每次选择的基准值为中位数的几率

时间复杂度

最坏时间复杂度

每次基准值都是最大 (或最小)值时,所需递归次数最多,有两种情况:

  1. 数组有序时,每次使用最后 1 位(或第 1 位)作为基准值
 1  2  3  4  5  6  7  8
                      ^
 1  2  3  4  5  6  7 [8]
                   ^
 1  2  3  4  5  6 [7]
                ^
 1  2  3  4  5 [6]
             ^  
 1  2  3  4 [5]
          ^  
 1  2  3 [4]
       ^  
 1  2 [3]
    ^ 
 1 [2]
 ^ 
[1]
  1. 随机选择时,每次选择到最大(或最小)的一位
 6  7  3  4  8  1  2  5
             ^
 6  7  3  4  1  2  5 [8]
    ^         
 6  3  4  1  2  5 [7] 8
 ^ 
 3  4  1  2  5 [6] 7  8
             ^ 
 3  4  1  2 [5] 6  7  8
    ^ 
 3  1  2 [4] 5  6  7  8
 ^
 1  2 [3] 4  5  6  7  8
    ^
 1 [2] 3  4  5  6  7  8
 ^
[1] 2  3  4  5  6  7  8

此时递归次数为 n + 1,平均每次排序 ½ n 个数。所以最坏时间复杂度:O(n^2)。

最好时间复杂度

如果每次选择中位数作为基准值,递归次数会减少么?其实不会减少,但递归中遍历的次数会减少。如果每层遍历看成 n 次的话,可以用下面的这个图表示:

快速排序的几种实现方式
图片来自《算法图解》

所以最好时间复杂度为:O(n * log n)

平均时间复杂度

最坏时间复杂度的情况很少见,所以平均时间复杂度就是最好时间复杂度 O(n * log n)

空间复杂度

每次递归均会使用额外空间,所以空间复杂度跟递归次数有关。

最坏时间复杂度时,最坏空间复杂度也为 O(n)。最好时间复杂度时时,虽然递归没有减少,但当只有 1 个或 0 个元素时,没有使用额外空间,直接返回,所以最好空间复杂度为 O(log n)。平均时间复杂度也为 O(log n)。

第 1 种实现因为使用额外数组,最坏空间复杂度为 O(n^2),最好空间复杂度为 O(n * log n),

测试代码

import logging

logging.basicConfig(level=logging.INFO)

def main():
    # nums = [3, 2, 1, 5, 6, 4]
    # 针对第 1 种
    print(Solution().quicksort(nums))
	
    # 针对第 2、3 种
    # Solution().quicksort(nums)
    # print(nums)


if __name__ == '__main__':
    main()

测试用例

[3, 2, 1, 5, 6, 4]

[3, 2, 1, 5, 6, 4, 4, 1]

[6, 5, 3, 1, 8, 7, 2, 4]

[]

延伸阅读

上一篇:选择行作为MySQL中的列?


下一篇:724. Find Pivot Index