快速排序 Fast Sort

思路：
每次从数组中抽取第一个元素作为temp元素，即当前round中要找到“正确”位置的元素，所谓“正确”的位置就是所有这个位置左边的数，都小于当前这个数(temp)，而所有右边的数，都大于当前的这个数(temp)。

怎么找到“正确”的位置：low，high两个index分别从数组的左右向中间靠拢，当high index对应的值比temp小，则将high index对应的值赋给low index对应的值；当low index对应的值比temp大，则将low index对应的值赋给high index对应的值，直到low==high为止，且这个index就是这个数“正确”的位置。

一趟结束后，分别对该元素左右两边的子数组继续进行以上操作，直至子数组变为只有一个元素的数组，即结束，并且于此同时，数组中的所有元素，也就都排好序了。
关键词：递归
时间复杂度 O(nlogn)
空间复杂度 O(logn) //虽然看起来，每趟排序只有一个temp变量的空间消耗，但需要栈空间来实现递归，所以，这里的空间指的是用来实现递归的栈空间

var array = [2,1,3,4,8,6,3,2,8,4];

function fastSort(array,low,high) {
    if(low>=high) {return}; // Only one element in sub-array, which means the sort should end
    var temp = array[low]; // low and high should never change in each round to decide the border of next round
    var i = low; 
    var j = high;
        while(i!=j){ // i==j means you find the correct position
            while(i<j && array[j]>=temp) {
                j--; //Too late position for temp
            }
            if(array[j]<temp){
                array[i]=array[j]; // assign the smaller element to low index (whic is 'i' currently)
            }
            while(i<j && array[i]<=temp) {
                i++; // Too former position for temp
            }
            if (array[i]>temp) {
                array[j]=array[i]; // assign the bigger element to high index (whic is 'j' currently)
            }
        }
        array[i] = temp; //i==j, assign the temp to the correct position. Each time array is more ordered
    fastSort(array,low,i-1); // do the same for left sub-array
    fastSort(array,j+1,high); // do the same for right sub-array
    return array; // return the final result
}

console.log(fastSort(array,0,array.length-1));