快速排序填坑口诀

Ocean 发布于2019-07-01 12:42 / 2495人阅读

摘要：直接默写出快速排序还是有一定难度的，所以一定要弄清楚原理再去记忆而不是去硬背。快速排序是于年提出的一种划分交换排序。

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此在很多笔试面试中出现的几率很高。

直接默写出快速排序还是有一定难度的，所以一定要弄清楚原理再去记忆而不是去硬背。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-Conque)。

最常见的实现方法是"填坑法"，它的实现步骤如下：

选定数列头元素为基准元素pivot，并记住这个位置index，这个位置相当于一个"坑"。

设置两个指针left和right，分别指向数列的最左和最右两个元素。

接下来从right指针开始，把指针所指向的元素和基准元素做比较，如果比pivot大，则right指针向左移动；如果比pivot小，则把所指向的元素放入index对应的位置。

将被放入坑中的元素(right指针移动之前指向的元素)之前的位置赋值给index让这个位置变成一个新的"坑"，同时left指针向右移动一位。

接下来切换到left指针进行比较，如果left当前指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把元素放入坑中，left指向的位置赋值给index，使其变成一个新的"坑"，同时right指针向左移动一位。

重复步骤3，4，5直到left等于right时，将pivot放入left和right重合的位置，此时数列中比pivot小的元素都在pivot左边，比pivot大的都在pivot元素位置的右边。

获取pivot的位置pivotIndex，分而制之，将pivotIndex左侧和右侧的子数列分别重复上述步骤1～6，直到不能拆分子数列为止，整个数列就是一个从头开始递增的数列。

具体的代码实现如下：

= $left) {
            // right 指针从右向左进行移动，如果当前值小于基准值则将当前元素放到坑中，当前元素的位置变成新坑，left向右移动一个位置，切换到left进行比较，否则right往左移动一个位置继续用新元素的值与基准值进行比较
            while ($right >= $left) {
                if ($arr[$right] < $pivot) {
                    $arr[$dataIndex] = $arr[$right];
                    $dataIndex = $right;
                    $left++;
                    break;
                }
                $right--;
            }

            // left 指针从左往右移动，如果当前值大于基准值则将当前元素放到坑中，当前元素变为新坑，right向左移动一个位置，切换到right进行比较，否则left往右移动一个位置继续与基准值进行比较
            while($right >= $left) {
                if ($arr[$left] > $pivot) {
                    $arr[$dataIndex] = $arr[$left];
                    $dataIndex = $left;
                    $right --;
                    break;
                }
                $left ++;
            }

        }

        $arr[$dataIndex] = $pivot;
        return $dataIndex;
    }

    public function quickSort(&$arr, $startIndex, $endIndex)
    {
        // startIndex大于等于endIndex的时候递归结束
        if ($startIndex >= $endIndex) {
            return ;
        }
        $pivotIndex = $this->partition($arr, $startIndex, $endIndex);
        $this->quickSort($arr, $startIndex, $pivotIndex - 1);
        $this->quickSort($arr, $pivotIndex + 1, $endIndex);
    }

}

$quickSortClass = new quickSortClass();
$arr = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85];
$quickSortClass->quickSort($arr, 0, count($arr) - 1);

var_dump($arr);

填坑法的口诀如下

1．$left=strart; $right = end; $pivot=$arr[$left]; 第一个坑为$arr[$left]

2．$right--由后向前找比$pivot小的数，找到后挖出此数填到前一个坑$arr[$left]中， $arr[$right]变成新坑。

3．$left++由前向后找比$pivot大的数，找到后也挖出此数填到前一个坑$arr[$right]中。

4．重复执行2，3二步，直到$left==$right，将基准数$pivot填入$arr[$left]中。

GPU云服务器云服务器快速排序函数快速排序算法 php快速排序 python快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31302.html

数据结构与算法（二）：带你读懂冒泡排序（Bubble Sorting）

摘要：经过一次冒泡排序，最终在无序表中找到一个最大值，第一次冒泡结束。也是我们后面要说的冒泡排序的优化。冒泡排序只执行第一层循环，而不会执行第二层循环。因此冒泡排序的时间复杂度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...

chuyao 2019-08-19 11:46 评论0 收藏0
JavaScript系列——JavaScript同步、异步、回调执行顺序之经典闭包setTimeou

摘要：同步异步回调傻傻分不清楚。分割线上面主要讲了同步和回调执行顺序的问题，接着我就举一个包含同步异步回调的例子。同步优先回调内部有个，第二个是一个回调回调垫底。异步也，轮到回调的孩子们回调，出来执行了。同步、异步、回调？傻傻分不清楚。大家注意了，教大家一道口诀：同步优先、异步靠边、回调垫底（读起来不顺）用公式表达就是：同步 => 异步 => 回调这口诀有什么用呢？用来对付面试的...

lewif 2019-08-29 12:21 评论0 收藏0
JavaScript系列——JavaScript同步、异步、回调执行顺序之经典闭包setTimeou

摘要：同步异步回调傻傻分不清楚。分割线上面主要讲了同步和回调执行顺序的问题，接着我就举一个包含同步异步回调的例子。同步优先回调内部有个，第二个是一个回调回调垫底。异步也，轮到回调的孩子们回调，出来执行了。同步、异步、回调？傻傻分不清楚。大家注意了，教大家一道口诀：同步优先、异步靠边、回调垫底（读起来不顺）用公式表达就是：同步 => 异步 => 回调这口诀有什么用呢？用来对付面试的...

rockswang 2019-08-20 15:32 评论0 收藏0
九乘九口诀表和乘法口诀表

摘要：程序效果九乘九口诀表乘法口诀表在这里我用两幅运行效果给大家看看，这样就知道不同之处了。乘法口诀表题目内容实现一个函数，打印乘法口诀表，口诀表的行数和列数自己指定。其实大致的性质是跟乘法口诀表一样都是使用循环嵌套。大家好，我是泽奀。这篇文章的代码是C语言中比较简单的程序，也是初学者必要学会的...

olle 2021-09-02 15:15 评论0 收藏0