文章目录
  1. 1. 原文代码
  2. 2. 代码段说明
  3. 3. 其他

原文地址:Functional Snippet #3: Functional Quicksort

原文代码

1
2
3
4
5
6
7
8
9
10
func qsort(input: [Int]) -> [Int] {
if let (pivot, rest) = input.decompose {
let lesser = rest.filter { $0 < pivot }
let greater = rest.filter { $0 >= pivot }
return qsort(lesser) + [pivot] + qsort(greater)
} else {
return []
}
}

代码段说明

  • 使用系列博文第一篇的decompose函数,递归实现快速排序。
  • 没有考虑效率和内存的使用情况。
  • 函数也比较简单,使用数组中第一个元素作为分割点,把剩余的数组用数组自带的filter方法分成2部分,一部分是所有小于第一个元素的,一部分是所有大于等于第一个元素的。然后使用递归分别对这2部分使用qsort排序。

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
extension Array {
var decompose : (head: T, tail: [T])? {
return (count > 0) ? (self[0], Array(self[1..<count])) : nil
}
}
func qsort(input: [Int]) -> [Int] {
if let (pivot, rest) = input.decompose {
let lesser = rest.filter { $0 < pivot }
let greater = rest.filter { $0 >= pivot }
return qsort(lesser) + [pivot] + qsort(greater)
} else {
return []
}
}
var input: [Int] = [1, 2, 3, 7, 4]
var result = qsort(input)
result //result = [1, 2 ,3, 4, 7]

其他

其实Swift中数组有自带的sort方法:

1
2
3
4
input.sort{
return $0 < $1
}
input //input = [1, 2 ,3, 4, 7]

需要注意的是,自带的sort方法,是mutating的。也就是说,直接修改数组的排序。
这里留下一个问题,如果我们不需要修改源数组,而是赋值给一个新数组。使用sort方法,应该怎么做?我想到的是给一个临时数组,因为Swift数组是值类型,是拷贝的,所以临时数组不会随着源数组变化而变化,在sort完成之后,把临时数组赋值给源数组:

1
2
3
4
5
6
7
8
9
10
11
12
let temp = input
input.sort{
return $0 < $1
}
//do something with sorted array
//...
//put to original array
input = temp
result
input

完整代码放在Github

文章目录
  1. 1. 原文代码
  2. 2. 代码段说明
  3. 3. 其他