内排序5：快速排序

快速排序（划分排序）又被认为是对泡排序的一种改进。在各种排序方法中，这种方法的元素之间的比较次数较少，因而速度较快，被认为是目前最好的内排序方法之一。
在跑排序中，元素的比较和交换动作是在相邻元素之间进行的，而快速排序是在两端进行的，因而，总的比较和移动的次数减少。

核心思想：在当前参加排序的序列（ks,ks+1,...,kt）中任意选择一个元素（通常称该元素为分界元素或者基准元素），把小于等于分界元素的所有元素都移动到分界元素的前边，把大于等于分界元素的所有元素都移动到分界元素的后边，这样，分界元素正好处在排序的 最终位置上，并且把当前参加排序的序列分成前后两个子序列。然后分别的对这两个子序列递归地进行上述过程，直到使得所有元素都到达整个排序后它们应处的最终位置上。
排除过程中需要设置两个整形变量i和j，每次排除的初始，i给出当前参加排序序列中第1个元素的位置（即s）,j给出当前参加排序序列的最后一个元素的位置（即t+1）,这样，整个快速排序过程可以归纳为执行以下步骤：
1.反复执行i+1送i的动作，直到ki>=ks或者i==t；然后反复执行j-1送j的动作，直到kj<=ks或者j==s。
2.若i<j，则将ki与kj交换位置，然后重复步骤1、2或者3.
3.若i>=j，则将kj与ks交换位置，然后分别递归地对（ks,...,kj-1）和（kj+1,...,kt）中长度大于1的子序列执行上述过程，直到整个序列排序结束。

具体算法如下：

function quick(arr, s, t) {
    let i, j, temp
    if ( s<t ) {
        i = s
        j = t+1
        while (1) {
            do {
                i++
            } while (!(arr[i]>arr[s] || i==t ));
            do {
                j--
            } while (!(arr[j]<arr[s] || j==s));
            if ( i<j ) {
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            } else {
                break;
            }
        }
        temp = arr[s]
        arr[s] = arr[j]
        arr[j] = temp
        arguments.callee(arr, s, j-1)
        arguments.callee(arr, j+1, t)
    }
}
function quickSort(arr) {
    let n = arr.length
    quick(arr, 0, n-1)
    return arr
}

let arr = [5,3,8,1,9,2,7,4,6,10]
quickSort(arr)

性能：
时间复杂度：最坏O(n2)，平均O(nlog2n)。
空间复杂度：最坏O(n)，平均O(log2n)。
是不稳定性排序。
如果各个部分的分界元素恰好是最大值元素，快排就会倒退为”慢速排序“。因此，在选择确定分界元素方法还是应该尽可能的小心。至于如何有效的选择分解元素，可参考其他资料。