不积跬步之快速排序

快速排序使用了分治思想来实现。

和冒泡排序一样，快速排序也属于交换排序，通过元素直接的比较和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮中只把一个元素冒泡到数列的一端，而快速排序则是：每一轮挑选一个基准元素。并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边。从而把数列拆解成两个部分。

这种思路就是分治疗法。

具体实现上则又分两种：
1.双边循环法
2.单边循环法

双边循环法

/**
 * 快速排序
 * */

function quickSort(array,startIndex,endIndex){
        //递归结束条件：startIndex大于或等于endIndex
        if(startIndex >= endIndex){
                return ;
        }
        
        //得到基准元素位置
        let pivotIndex = partition(array,startIndex,endIndex);
        //左边的循环
        quickSort(array,startIndex,pivotIndex -1);
        //右边循环
        quickSort(array,pivotIndex+1,endIndex);
}

function partition(array,startIndex,endIndex){
        //取第一个位置或者随机位置的元素作为基准元素。
        let pivot = array[startIndex];
        let left = startIndex;
        let right = endIndex;
        
        while (left !== right){
                //和我们的基准线相比较，如果大于基准线，就向左移动，直到截止
                while (left < right && array[right] > pivot){
                        right --;
                        console.log("right==",right)
                }
                
                //控制left指针向右移动，也就是和基准线比较，如果小基准线就继续向右移动，直到碰到大于的或者是
                while (left < right && array[left] <= pivot){
                         left++;
                        console.log("left==",left)
        
                }
                
                //交换left和right指针所指向的元素，也就是位置互换
                if(left < right){
                        let p = array[left];
                        array[left] = array[right];
                        array[right] = p;
                }
        }
        
        //基准线和指针重合点交换
        array[startIndex] = array[left];
        array[left] = pivot;
        return left;
}

单边循环法

双边循环法是从数组的两边交替遍历元素，虽然直观，却比较繁琐。而单边循环法则简单很多。

只从数组的一边对元素进行遍历和交换。

[4,7,3,5,6,2,8,1]

开始和双边循环法相似，首先要选定基准元素pivot，同时设置一个mark指针指向数列的起始位置。这个mark指针代表小于基准元素的区域边界。

pivot=4;
mark=0;

接下来从基准元素的下一个位置开始遍历。
如果遍历到元素大于基准 元素的，就继续往后遍历。

如果遍历到的元素小于基准元素，则需要做两件事儿。
第一：把mark指针右移一位，因为小于pivot的区域边界增大了1；
第二：让最新遍历到的元素和mark指针所在的位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。

好，上代码：

//单边循环法

function quickSort(array,startIndex,endIndex){
        //递归结束条件：startIndex大于或等于endIndex
        if(startIndex >= endIndex){
                return ;
        }
        
        //得到基准元素位置
        let pivotIndex = partition(array,startIndex,endIndex);
        //左边的循环
        quickSort(array,startIndex,pivotIndex -1);
        //右边循环
        quickSort(array,pivotIndex+1,endIndex);
}

//单边循环法
function partition(array,startIndex,endIndex){
        
        let pivot = array[startIndex];
        let mark = startIndex;
        
        for(let i = startIndex+1;i<=endIndex;i++){
                if(array[i] < pivot){
                        mark++;
                        let p = array[mark];
                        array[mark] = array[i];
                        array[i] = p;
                }
        }
        array[startIndex] = array[mark];
        array[mark] = pivot;
        return mark;
}

over...