小撒是一只好学的小鸭子，这天，小撒在学习算法
快速排序（quick sort）
快速排序同样试用了分治的思想。
快速排序的过程如下：
- 选择数组中的一个元素为基点（pivot），通常选择数组头部的元素，也可以随机选择一个元素来降低快排遭遇最差情况的可能。
- 将所有比基点小的元素移到基点左侧，大的元素移到右侧
- 以基点为界，对左右的子数组执行步骤
1、2，直至子数组包含1个或更少的元素
让我们用图来说明这个过程：
快排的递归过程
如图所示，我们需要明白的是，在以4为基点移动元素后，由于左侧都更小、右侧都更大，因此在最终的排序结果中，4应当就出现在这个位置：即4已经被排序到了正确的位置。因此接下来我们只需处理它的左右子数组。
移动过程
接下来看看每一次的移动过程：
基于基点移动过程
在图示中，我们以数组第一个元素4为基点进行移动。其中涉及到了几个位置的标志位：
-
x：代表当前基点元素位于数组中的下标 -
i：代表下一个判断的元素的下标（事实上i始终等于x + 1） -
j：代表尾部的元素下标
这里j所代表的是当下一个被判断的元素大于基点时，被交换到的位置。在最初j指向数组尾部，每当有元素被移动到数组尾部时，j所指向的位置便向左移动一格。移动后，x右侧（i指向的）是从尾部交换过来的尚未被处理的元素。
而当几点元素小于其左侧元素时，则交换两个元素的位置，并继续处理再右侧的元素。
移动过程的终止为x与j相遇。
代码示例（js）
const sort = (arr, start, end) => {
if (start >= end) return
const pivot = arr[start]
let x = start, i = start + 1, j = end
while (x < j) {
if (arr[i] > pivot) {
swap(arr, i, j)
j--
} else {
swap(arr, x, i)
x = i
i++
}
}
sort(arr, start, x - 1)
sort(arr, x + 1, end)
}
小结
快速排序在最差情况下的运行时间为Θ(n^2)，而期望运行时间为Θ(n * log(n))。同时快排也是一种原地排序方法，在编写代码时也较为直观，因此它可谓是排序的最实用选择。
