QuickSort_快速排序

实现方法一：

 1.  i 从左到右找大于 pivot 的数， j 从右至左找小于pivot的数

2.  pivot 一定与 j 交换

3. i 和 j 都可以超出数组的边界，即 i 可以指向最后一个元素的后面，j 可以指向 pivot（pivot取最左边的元素时）

pivot = 15

15 10 13 27 12 22 20 25

      i10                          j25    i从左到右找大于15的数 j相反

                i27 j12   交换

15 10 13 12 27 22 20 25

i12 j27 -> j12 i27   j12 和 pivot 交换

12 10 13          15 27 22 20 25

pivot = 12  i = 13，j = 10，10和12交换

10 12 13           15      27 22 20 25

pivot = 27  i = 25之后的位置，j = 25 与27交换

10 12 13 15      25 22 20     27

pivot = 25  i = 20之后的位置，j = 20 与25交换

10 12 13 15     20 22     25 27

pivot = 20  i=22   j=20 与20交换

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

实现方法二：（Foundation of Algorithm_lec05）

define P ≡ 0 ≤ fe ≤ next ≤ fg ≤ n and A[0 . . . fe − 1] < p and A[fe . . . next − 1] = p and A[fg . . . n − 1] > p and (p ∈ A[next . . . fg − 1] or fe < next)

Initialization: next,fe,fg ← 0,0,n

assert: P

Loop:

while next < fg

    assert: P and next < fg

    if A[next] < p

        swap A[fe] and A[next]

        fe, next ← fe + 1, next + 1

        assert: P

    else if A[next] > p

        swap A[next] and A[fg − 1]

        fg ← fg − 1

        assert: P

    else

        next ← next + 1

        assert: P and fe < next

assert:Pandnext≥fgandfe<next =⇒ R

复杂度：

最坏时间复杂度 O(n*n)

最好、平均时间复杂度 O(nlogn)

一般空间复杂度不是指递归调用的层数，是指额外使用的空间。

快速排序空间复杂度主要指递归调用的层数：

最坏空间复杂度为O(n)

最好、平均空间复杂度为O(logn)