快速排序

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序时间复杂度分析

快速排序最优的情况就是每一次取到的元素都刚好平分整个数组；

最差情况下时间复杂度

    **最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)**<br />**     这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;**<br />**     综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )**<br />

平均时间复杂度

   ** 快速排序的平均时间复杂度也是：O(nlogn)**

function swap(A, i, j) {
            [A[i], A[j]] = [A[j], A[i]]
        }
        function partition(A, first, last) {
            var i=first, j=last-1;
            const pivot = A[j]
            while(i !== j){
                if(A[i] <= pivot){
                    i++
                }else{
                    swap(A, i, --j)
                }
            }
            swap(A, j, last-1)
            return j
        }
        function qsort(A, first=0, last=A.length){
            if(last - first <= 1) return;
            const a = partition(A, first, last)
            qsort(A, first, a)
            qsort(A, a+1, last)
        }
        const A = [10, 80, 30, 90, 40, 50, 70]
        qsort(A)
        console.log(A)