快速排序———总结

2018-06-11

快速排序

排序算法是计算机科学最古老，最基本的课题之一了，要想成为合格的程序员，还是要理解和掌握下各种排序算法。

快排在前端面试中问到的挺多的，想着不要丢分就总结下知识点，忘记的时候过来看看。

快排的方法就是就是找个基准，然后比大小，基准左边的永远小于基准，基准右边的永远大于或等于基准，然后，基准左边的划分为一个区域，基准右边的划分为一个区域，在区域内重复操作，直到，划分区域只有1个为止

比如我们找中间的基准为6

1	[1,2,3,4,5,6,2,3,45,6]

第一趟快排下来就是

1	[1,2,3,4,5,3] 6 [45,6]

第二趟下来就是

1	[1,2] 3 [4,5,3] 6 6 45

第三趟下来就是

1	1 2 3 [4,3] 5 6 6 45

第四趟下来就是

1	[1] [2] [3] [3] [4] [5] [6] [6] [45]

排序完成

可以看到的规律是，和基准比较，比基准小的就放在左边，大于或等于就放在右边，左边的称为一个新区域，右边的成一个新区域，然后重新选择左边的基准，重新选择右边的基准，只到没有区域为止或区域为1时结束。
可以用js一行代码就实现。用filter（数组的迭代方法）,concat（数组的合并方法）,slice（切分方法）

1
2
3

function quickSort(arr){
    return arr.length<=1 ? arr :quickSort(arr.slice(1).filter(item=>item<arr[0])).concat(arr[0],quickSort(arr.slice(1).filter(item => item >= arr[0])))
}

可能这种方法不容易理解，而且也用了filter对时间复杂度之类的可能会产生影响，所以就用最原始的方法阐述下
没用阮一峰大神的博客的那个版本，因为那种写法每次都生成一个空数组，空间复杂度会很大，而且每次都重新排序会很慢，但是很好理解。
阮一峰大神的版本地址点击这里
下面是我们实现的不添加新数组空间的快排

//快排主函数
function quickSort(arr,left,right){
    var len = arr.length,
        Index,
        left = typeof left !=='number'?0:left,
        right = typeof right !=='number'? len -1 :right;
        //len是数组长度，Index是快排分组边界索引，left是边界左边的值没有则是0，right是边界右边的值，没有则是长度减一
        
        //如果需要排序的起始索引小于终止索引则执行排序;递归的终止条件；
        if(left<right){
            //确定索引用一个partition函数返回
            Index = partition(arr,left,right);
            //返回左边的元素均小于arr[Index]
            quickSort(arr,left,Index - 1);
            //返回右边的元素均大于arr[Index]
            quickSort(arr,Index + 1,right);
        }
        console.log('区间索引值',Index)
        console.log('左',left)
        console.log('右',right)
        console.log('总的arr',arr)
        return arr;
}
//划分区间函数
function partition(arr,left,right){
    var pivot = left,
        index = pivot + 1;
    //从左到右比较一遍
    for(var i = index;i <= right;i++){
        if(arr[i]<arr[pivot]){
            swap(arr,i,index);
            index++
        }
    }
    //交换pivot和index-1索引的值之后index-1索引左边全都是小于arr[index-1]的元素；
    swap(arr,pivot,index - 1);
    return index-1
}
//位置交换函数
function swap(arr,i,j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

还有以下方法
实现快排的关键在于，先在数组中选一个数作为基数，接着以基数为中心将数组中的数字分为两部分，比基数小的放在数组的左边，比基数大的放再数组的右边，接下来就可以用递归的思路对基数的左右两边进行排序。
总结为以下三个步骤

1.从数组中取出一个数作为基数
2.分区，将数组分为两部分，比基数小的放在数组的左边，比基数大的放在数组的右边。
3.递归使左右区间重复第二步，直至各个区间只有一个数。

下面这方法是两端分别扫描，然后交换最后达到排序效果

function quick(arr,left,right){
    var len = arr.length,
        partitionIndex,
        left = typeof left !== 'number' ? 0 : left,
        right = typeof right !== 'number' ? len - 1 : right;

    if(left < right){//递归的边界条件，当 L == R时数组的元素个数为1个
        var pivot = arr[left];//最左边的元素作为中轴
        var i = left+1,j = right
        //当i == j时，i和j同时指向的元素还没有与中轴元素判断，
        //小于等于中轴元素，i++,大于中轴元素j--,
        //当循环结束时，一定有i = j+1, 且i指向的元素大于中轴，j指向的元素小于等于中轴
        while(i<=j){
            while(i <= j && arr[i]<=pivot){//往左边比
                i++
            }
            while(i<=j&&arr[j]>pivot){//往右边比
                j--
            }
            //当 i > j 时整个切分过程就应该停止了，不能进行交换操作
            //这个可以改成 i < j， 这里 i 永远不会等于j， 因为有上述两个循环的作用
            if(i<=j){
                swap(arr,i,j);
                i++;
                j--;
            }
        }
         //当循环结束时，j指向的元素是最后一个（从左边算起）小于等于中轴的元素
        swap(arr,left,j)//将中轴元素和j所指的元素互换
        quick(arr,left,j-1)//递归左半部分
        quick(arr,j+1,right)//递归右半部分
    }
    return arr;
}
function swap(arr,i,j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}