函数式快排(Functional Quicksort)

文章翻译自objc，原文连接：『Functional Quicksort』

下面是一个快排的变体实现，并没在速度上有所改良，大多快排实现的空间复杂度也是恒定的。不过，这段代码应该是最简洁最清晰的一种实现：

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 []
	}
}

这段代码是构建在之前的拆解数组基础之上的:如果数组不为空，就以第一个数组元素为参照，把数组拆分到两个新的数组：第一个数组中包含的都是比参照小的元素，第二个数组是包含的大于或者等于参照的元素。然后，排序第一个数组，加上参照，加上排序后的第二个数组，就ok了。