算法-快速排序

快速排序

快速排序是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)

算法描述

利用分治法可将快速排序的分为三步:

  1. 在待排序的数组中选择一个元素作为”基准”(pivot)。
  2. 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  3. 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

Swift 实现

简单版

便于理解将带排序数组分为三部分。这样排序并不快,因为对同一个数组进行了三次 filter

1
2
3
4
5
6
7
8
func quicksort<T: Comparable>(_ list: [T]) -> [T] {
guard list.count > 1 else { return list }
let pivot = list[list.count / 2]
let less = list.filter { $0 < piovt }
let equal = list.filter { $0 == piovt }
let greater = list.filter { $0 > piovt }
return quickSort(less) + equal + quickSort(greater)
}

Lomuto’s partitioning scheme

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func quicksortLomuto<T: Comparable>(_ list: inout [T], low: Int, high: Int) {
func partitionLomuto(_ list: inout [T], low: Int, high: Int) -> Int {
let pivot = list[high]
var i = low
for j in low ..< high {
if list[j] <= pivot {
list.swap(i, j)
i += 1
}
}
list.swap(i, high)
return i
}
if low < high {
let p = partitionLomuto(&list, low: low, high: high)
quicksortLomuto(&list, low: low, high: p - 1)
quicksortLomuto(&list, low: p + 1, high: high)
}
}

Hoare’s partitioning scheme

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func quicksortHoare<T: Comparable>(_ list: inout [T], low: Int, high: Int) {
func partitionHoare(_ list: inout [T], low: Int, high: Int) -> Int {
let piovt = list[low]
var i = low - 1
var j = high + 1

while true {
repeat { j -= 1 } while list[j] > piovt
repeat { i += 1 } while list[i] < piovt

if i < j {
list.swap(i, i)
} else {
return i
}
}
}
if low < high {
let p = partitionHoare(&list, low: low, high: high)
quicksortHoare(&list, low: low, high: p)
quicksortHoare(&list, low: p + 1, high: high)
}
}

对比

  1. Hoare分区算法比 Lomuto分区算法更高效,因为前者比后者少了三倍的swap, 即使在所有元素都相等的情况下依然能保持效率
  2. Lomuto分区算法一样,当数组为已排序数组事,Hoare分区算也会达到 O(n²)的时间复杂度,同时也是不稳定排序
  3. Hoare分区算法返回的值不一定是 pivot 在已排序数组里的位置。

算法分析

  1. 当分区选取的基准元素为待排序元素中的最大或最小值时,为最坏的情况,时间复杂度和直接插入排序的一样,移动次数达到最大值

    1
    Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n²)

    最大时间复杂:O(n²)

  2. 当分区选取的基准元素为待排序元素中的”中值”,为最好的情况
    最优时间复杂度:O(nlog n)。
  3. 空间复杂度:O(log2n)
  4. 当待排序元素类似[6,1,3,7,3]且基准元素为6时,经过分区,形成[1,3,3,6,7],两个3的相对位置发生了改变,所是快速排序是一种不稳定排序

Reference