算法图解- 第4章 快速排序

第四章 快速排序

# 分而治之( D&C ) - (divide and conquer)

#快速排序
　　- 基线条件(退出程序) 和 递归条件(调用程序)
　　- 选择一个基准值 作为递归条件
　　- 基准值 可以是数组中任何一个元素 【注设定了基准值后要从原数组删除】

eg:对数组从小到大排序，以任意一个元素a为基准值，将小于a的所有数放在一起，将大于a的所有数放在一起。最后通过递归调用完成排序

/**
     * @method: quickSort
     * @des: 快速排序 - 基线条件退出  递归条件调用
     * @return: 
     */
    function quickSort(arr){
        //基线条件：为空 或 只有一个元素时，是有序的。无需排序
        if (arr.length <= 1) { 
            return arr;
        } else {
            // 基准值，递归条件 【注意：基准值设定后需从原数组删除】 基准值可以是数组的任何值
            var pivot = arr.splice(0,1);  //splice改变原数组，且返回删除后的值
            
            //存放所有小于基准值的元素组成的子数组
            var left = []; 

            //存放所有大于基准值的元素组成的子数组
            var right = [];

            for (var i = 0; i < arr.length; i++) {
                if (arr[i] < pivot) {
                    left.push(arr[i]);
                } else {
                    right.push(arr[i]);
                }
            }
            // console.log(left,pivot,right);

            //递归   -  链接左数组、基准数构成的数组、右数组          
            return quickSort(left).concat(pivot,quickSort(right));
        }
                                                                                              

    }          
    var list = [5, 1, 6, 0, 9, 20, 60, 8, 66, 4];
    console.log( quickSort(list) );