快速排序 - 灰太狼的狼堡

235 字

1 分钟

快速排序

2023-09-30

Code

算法

核心思想：分而治之，选一个基准值（Pivot），把数组分成两边，小的放左边，大的放右边，然后继续递归直到有序。#

朴素的基准是选第一个 or 最后一个 or 中间，算法容易退化直 $O(n^2)$ ，随机选择 $Pivot$ 能使划分在期望意义上是均匀的，保证算法的期望时间复杂度为 $O(n\log n)$ 。

以下是Go语言的实现版本

1
func sortArray(nums []int) []int {
2
  var quickSort func(l, r int)
3

4
  quickSort = func(l, r int) {
5
    if l >= r {
6
      return
7
    }
8

9
    // 随机选择 pivot，并交换到区间起点
10
    pivotIdx := l + rand.Intn(r-l+1)
11
    nums[l], nums[pivotIdx] = nums[pivotIdx], nums[l]
12
    pivot := nums[l]
13

14
    i, j := l+1, r
15
    for i <= j {
16
      for i <= j && nums[i] < pivot {
17
        i++
18
      }
19
      for i <= j && nums[j] > pivot {
20
        j--
21
      }
22
      if i <= j {
23
        nums[i], nums[j] = nums[j], nums[i]
24
        i++
25
        j--
26
      }
27
    }
28

29
    // 把 pivot 放到最终位置
30
    nums[l], nums[j] = nums[j], nums[l]
31

32
    quickSort(l, j-1)
33
    quickSort(j+1, r)
34
  }
35

36
  quickSort(0, len(nums)-1)
37
  return nums
38
}