快速排序 - 容易中招的地方

2017-02-24 本文已影响254人 holysu

快速排序，也是一种二分的思想，选取一个基准数，然后将大于和小于基准的元素分别放置于基准数两边，然后继续按此方法分治基准数的两侧，直至最后一个元素。

那么快排的实现需要解决以下几个问题：

基准数的选择
元素的查找
递归调用
基准数的归位

对应处理：

通常选取头或者尾元素
一组一组的查找需要交换位置的元素
既然是递归，就一定要有终止递归的临界条件，要不然肯定会导致调用堆栈溢出
归位，查找相遇的位置和基准位元素互换

对于第二点，需要注意元素查找的先后顺序，以从小到大排序为例：

如果基准数选取的为arr[low] ，那么必须先从高位high查找到小于pivot的数，然后再从低位low寻找大于pivot的数，交换；
如果基准数选取的为arr[high] ，那么必须先从低位low查找到大于pivot的数，然后再从高位high寻找小于pivot的数，交换；

原因是，当两侧的查找相遇时候，需要将基准数pivot 和相遇点元素的值交换以正确归位基准数pivot；也就是pivot = arr[low] 这种情况相遇点的元素值必须要小于pivot的值，如果先从低位low查找大于pivot的元素，最终停止的元素大于pivot的话就会导致归位失败；

要更清晰的看具体的差别，可以交换下面代码中的查找顺序，然后断点一步步查看差别；其实我们写代码，思路有了，输入输出的条件限制清晰后代码实现可能只需要花20%的时间，还有80%的时间则花在一步步的验证边界情形上；这边查找顺序的差别个人就断点调试了很多遍，也在纸上画出反例会出现的情况才得以印象深刻。

    /* 快速排序 */
    function quickSortUnit(arr,low,high){
        var temp,
            pivot = arr[high];
        while(low < high){      
            /* 查找顺序要和基准选取相反；
             pivot = arr[high] 则必须先从low开始；
             反之 pivot = arr[low]; 则必须先从high开始查找 */
            while(arr[low] <= pivot && low < high)
                low++; 
            arr[high] = arr[low];
            while(arr[high] >= pivot && low < high)
                high--;  
            arr[low] = arr[high];
        }
        // 校准，将基准移至正确位置
        arr[low] = pivot;
        return low;
    }

    function quickSort(arr,low,high){
         if(low >= high) return;
         var index = quickSortUnit(arr,low,high);
         quickSort(arr,low,index-1);
         quickSort(arr,index+1,high);
    }

附上一个网站 https://visualgo.net/sorting 可视化排序的过程

图片.png

快速排序 - 容易中招的地方

猜你喜欢

热点阅读