快速排序

//时间复杂度分析：
//最好的情况：整个数组被分为两个长度相等的子数组时， 时间复杂度为 O（nlogn）
//最坏的情况：待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列 （退化成冒泡排序的情况）时间复杂度为O（n的平方）
//平均时间复杂度为：O（nlogn）有可能改变相等元素的原始位置，所以快速排序是一种不稳定的排序。



//空间复杂度分析：
//首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；
//最优的情况下空间复杂度为：O(logn)；每一次都平分数组的情况
//最差的情况下空间复杂度为：O( n )；退化为冒泡排序的情况
//平均 O（nlogn）

//第一种
        var arr = [49, 38, 65, 97, 76, 13, 27, 48, 55, 4];
        function QuickSort(arr) {
            var len = arr.length;
            if(len<=1){ return arr; }
            var baseNum = arr[0];
            var left_arr = [];
            var right_arr = [];
            for(var i=1;i<len;i++){
                if(arr[i]<=baseNum){
                    left_arr.push(arr[i])
                }else{
                    right_arr.push(arr[i])
                }
            }
            left_arr = QuickSort(left_arr);
            right_arr = QuickSort(right_arr);
            return left_arr.concat(baseNum,right_arr);
        }
        console.log(QuickSort(arr)); //4, 13, 27, 38, 48, 49, 55, 65, 76, 97

//第二种
        var arr = [49, 38, 65, 97, 76, 13, 27, 48, 55, 4];
        function QuickSort(arr,i,j) {
            if(i<j){
            var left = i;
            var right = j;
            var baseNum = arr[left];
            while(i<j){
                while(arr[j]>baseNum && i<j){
                    j--
                }
                if(i<j){
                    arr[i] = arr[j]
                    i++
                }
                while(arr[i]<baseNum && i<j){
                        i++
                }
                if(i<j){
                    arr[j] = arr[i]
                    j--
                }
            }
            arr[i] = baseNum
            QuickSort(arr,left,i-1);
            QuickSort(arr,i+1,right);
            return arr
            }
        }
        console.log(QuickSort(arr,0,arr.length-1)); //4, 13, 27, 38, 48, 49, 55, 65, 76, 97