侯瑞哲的博客

Ruizhe's Blog

0%

快速排序的多种写法

发表于 Valine：

快速排序作为一种基础的算法，广泛用于各种语言的内置排序库中，其中java使用了双基准快速排序（主要是双基准更有效的利用了计算机的缓存机制）。它是一种原地的，空间复杂度为O(1)、时间复杂度O(nlogn)、不稳定的排序算法。分为切分，和递归两个步骤。其中切分的步骤可以帮助我们以O(n)的时间复杂度找到数组中某种排名为K的元素。然而在实际实现中，快排有一些小技巧，也是我们必须要掌握的一种算法。

以下给出python版本的实现代码。

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
class Solution:
    def quickSort(self, nums: List[int]):
        return self.quickSortHelper(nums, 0, len(nums) - 1)

    def quickSortHelper(self, nums, l, r):
        if l >= r:
            return
        pivot = self.partition(nums, l, r)
        self.quickSortHelper(nums, l, pivot - 1)
        self.quickSortHelper(nums, pivot + 1, r)

    # def partition(self, nums, l, r):
    #     ran = random.randint(l, r)
    #     nums[r], nums[ran] = nums[ran], nums[r]
    #     pivot = r
    #     right = l
    #     for i in range(l, r):
    #         if nums[i] <= nums[pivot]:
    #             nums[i], nums[right] = nums[right], nums[i]
    #             right += 1
    #     nums[right], nums[pivot] = nums[pivot], nums[right]
    #     return right

    def partition(self, nums, l, r):
        ran = random.randint(l, r)
        nums[l], nums[ran] = nums[ran], nums[l]
        pivot = l
        left = r
        i = l + 1
        while i <= left:
            if nums[i] >= nums[pivot]:
                nums[i], nums[left] = nums[left], nums[i]
                left -= 1
            else:
                i += 1
        nums[left], nums[pivot] = nums[pivot], nums[left]
        return left

两个partition的效果是一样的。

注意，我们使用一种随机方法，保证了我们的快排在遇到严格递增序列或者严格递减序列的时候，期望也是O(nlogn)时间复杂度的。这是一种随机方法，还有其他随机算法的实现。这种比较简单。而这个随机的步骤，也使得我们的快排不是稳定。