# andyRon/swift-algorithm-club-cn

Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
Images
Quicksort.playground

# 快速排序(Quicksort)

```func quicksort<T: Comparable>(_ a: [T]) -> [T] {
guard a.count > 1 else { return a }

let pivot = a[a.count/2]
let less = a.filter { \$0 < pivot }
let equal = a.filter { \$0 == pivot }
let greater = a.filter { \$0 > pivot }

return quicksort(less) + equal + quicksort(greater)
}```

```let list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
quicksort(list)```

## 一个例子

``````[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
``````

``````less:    [ 0, 3, 2, 1, 5, -1 ]
equal:   [ 8, 8 ]
greater: [ 10, 9, 14, 27, 26 ]
``````

``````[ 0, 3, 2, 1, 5, -1 ]
``````

``````less:    [ 0, -1 ]
equal:   [ 1 ]
greater: [ 3, 2, 5 ]
``````

``````[ 0, -1 ]
``````

``````less:    [ ]
equal:   [ -1 ]
greater: [ 0 ]
``````

`less`数组是空的，因为没有小于`-1`的值; 其他数组各包含一个元素。 这意味着我们已经完成了递归，现在我们返回以对前一个`greater`数组进行排序。

`greater`数组是:

``````[ 3, 2, 5 ]
``````

``````less:    [ ]
equal:   [ 2 ]
greater: [ 3, 5 ]
``````

``````less:    [ 3 ]
equal:   [ 5 ]
greater: [ ]
``````

``````[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27 ]
``````

## 分区

``````[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
``````

``````[ 0, 3, 2, 1, 5, -1, 8, 8, 10, 9, 14, 27, 26 ]
-----------------        -----------------
all elements < 8         all elements > 8
``````

``````[ 3, 0, 5, 2, -1, 1, 8, 8, 14, 26, 10, 27, 9 ]
``````

## Lomuto的分区方案

```func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
let pivot = a[high]

var i = low
for j in low..<high {
if a[j] <= pivot {
(a[i], a[j]) = (a[j], a[i])
i += 1
}
}

(a[i], a[high]) = (a[high], a[i])
return i
}```

```var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
let p = partitionLomuto(&list, low: 0, high: list.count - 1)
list  // show the results```

`low``high`参数是必要的，因为当在快速排序时并不一定排序整个数组，可能只是在某个区间。

``````[ 0, 3, 2, 1, 5, 8, -1, 8, 9, 10, 14, 26, 27 ]
*
``````

1. `a [low ... i]` 包含 `<= pivot` 的所有值
2. `a [i + 1 ... j-1]` 包含 `> pivot` 的所有值
3. `a [j ... high-1]` 是我们“未查看”的值
4. `a [high]`是基准值

In ASCII art the array is divided up like this: 用ASCII字符表示，数组按如下方式划分：

``````[ values <= pivot | values > pivot | not looked at yet | pivot ]
low           i   i+1        j-1   j          high-1   high
``````

``````[| 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low                                       high
i
j
``````

``````[| 10 | 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low                                        high
i
j
``````

``````[ 0 | 10 | 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low                                         high
i
j
``````

``````[ 0, 3 | 10 | 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low                                         high
i
j
``````

“values <= pivot”区域现在是`[0,3]`。 让我们再做一次......`9`大于枢轴，所以简单地向前跳：

``````[ 0, 3 | 10, 9 | 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low                                         high
i
j
``````

``````[ 0, 3, 2, 1, 5, 8, -1 | 27, 9, 10, 14, 26 | 8 ]
low                                        high
i                   j
``````

``````[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 10, 14, 26, 27 ]
low                                       high
i                  j
``````

** 注意：** 如果您仍然不完全清楚算法是如何工作的，我建议您在playground 试验一下，以确切了解循环如何创建这四个区域。

```func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let p = partitionLomuto(&a, low: low, high: high)
quicksortLomuto(&a, low: low, high: p - 1)
quicksortLomuto(&a, low: p + 1, high: high)
}
}```

```var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quicksortLomuto(&list, low: 0, high: list.count - 1)```

Lomuto方案不是唯一的分区方案，但它可能是最容易理解的。 它不如Hoare的方案有效，后者需要的交换操作更少。

## Hoare的分区方案

```func partitionHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
let pivot = a[low]
var i = low - 1
var j = high + 1

while true {
repeat { j -= 1 } while a[j] > pivot
repeat { i += 1 } while a[i] < pivot

if i < j {
a.swapAt(i, j)
} else {
return j
}
}
}```

```var list = [ 8, 0, 3, 9, 2, 14, 10, 27, 1, 5, 8, -1, 26 ]
let p = partitionHoare(&list, low: 0, high: list.count - 1)
list  // show the results```

``````[ -1, 0, 3, 8, 2, 5, 1, 27, 10, 14, 9, 8, 26 ]
``````

```func quicksortHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let p = partitionHoare(&a, low: low, high: high)
quicksortHoare(&a, low: low, high: p)
quicksortHoare(&a, low: p + 1, high: high)
}
}```

Hoare的分区方案是如何工作的？我将把它作为练习让读者自己弄清楚。:-)

## 选择一个好的基准

Lomuto的分区方案总是为基准选择最后一个数组元素。 Hoare的分区方案使用第一个元素。 但这都不能保证这些基准是好的。

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

``````   less than pivot: [ ]
equal to pivot: [ 1 ]
greater than pivot: [ 7, 6, 5, 4, 3, 2 ]
``````

``````   less than pivot: [ ]
equal to pivot: [ 2 ]
greater than pivot: [ 7, 6, 5, 4, 3 ]
``````

``````   less than pivot: [ ]
equal to pivot: [ 3 ]
greater than pivot: [ 7, 6, 5, 4 ]
``````

``````   less than pivot: [ 3, 2, 1 ]
equal to pivot: [ 4 ]
greater than pivot: [ 7, 6, 5 ]
``````

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

```func quicksortRandom<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let pivotIndex = random(min: low, max: high)         // 1

(a[pivotIndex], a[high]) = (a[high], a[pivotIndex])  // 2

let p = partitionLomuto(&a, low: low, high: high)
quicksortRandom(&a, low: low, high: p - 1)
quicksortRandom(&a, low: p + 1, high: high)
}
}```

1. `random(min:max:)`函数返回`min...max`范围内的整数，这是我们基准的索引。
2. 因为Lomuto方案期望`a[high]`成为基准，我们将`a[pivotIndex]``a[high]`交换，将基准元素放在末尾，然后再调用`partitionLomuto()`

## 荷兰国旗🇳🇱分区

``````[ values < pivot | values equal to pivot | values > pivot ]
``````

```func partitionDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int, pivotIndex: Int) -> (Int, Int) {
let pivot = a[pivotIndex]

var smaller = low
var equal = low
var larger = high

while equal <= larger {
if a[equal] < pivot {
swap(&a, smaller, equal)
smaller += 1
equal += 1
} else if a[equal] == pivot {
equal += 1
} else {
swap(&a, equal, larger)
larger -= 1
}
}
return (smaller, larger)
}```

• `[low ... smaller-1]` 包含`< pivot` 的所有值
• `[less ... equal-1]` 包含 `== pivot` 的所有值
• `[equal ... larger]`包含 `> pivot` 的所有值
• `[large ... high]` 是我们“未查看”的值

Note that this doesn't assume the pivot is in `a[high]`. Instead, you have to pass in the index of the element you wish to use as a pivot. 请注意，这并不假设基准处于`a[high]`。 而是，必须传入要用作基准的元素的索引。

```var list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
partitionDutchFlag(&list, low: 0, high: list.count - 1, pivotIndex: 10)
list  // show the results```

``````[ -1, 0, 3, 2, 5, 1, 8, 8, 27, 14, 9, 26, 10 ]
``````

```func quicksortDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let pivotIndex = random(min: low, max: high)
let (p, q) = partitionDutchFlag(&a, low: low, high: high, pivotIndex: pivotIndex)
quicksortDutchFlag(&a, low: low, high: p - 1)
quicksortDutchFlag(&a, low: q + 1, high: high)
}
}```

```public func swap<T>(_ a: inout [T], _ i: Int, _ j: Int) {
if i != j {
a.swapAt(i, j)
}
}```

## 扩展阅读

You can’t perform that action at this time.