专栏首页网管叨bi叨快速排序填坑口诀

快速排序填坑口诀

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

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

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

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

  1. 选定数列头元素为基准元素pivot,并记住这个位置index,这个位置相当于一个"坑"。
  2. 设置两个指针left和right,分别指向数列的最左和最右两个元素。
  3. 接下来从right指针开始,把指针所指向的元素和基准元素做比较,如果比pivot大,则right指针向左移动;如果比pivot小,则把所指向的元素放入index对应的位置。
  4. 将被放入坑中的元素(right指针移动之前指向的元素)之前的位置赋值给index让这个位置变成一个新的"坑",同时left指针向右移动一位。
  5. 接下来切换到left指针进行比较,如果left当前指向的元素小于pivot,则left指针向右移动;如果元素大于pivot,则把元素放入坑中,left指向的位置赋值给index,使其变成一个新的"坑",同时right指针向左移动一位。
  6. 重复步骤3,4,5直到left等于right时,将pivot放入left和right重合的位置,此时数列中比pivot小的元素都在pivot左边,比pivot大的都在pivot元素位置的右边。
  7. 获取pivot的位置pivotIndex,分而制之,将pivotIndex左侧和右侧的子数列分别重复上述步骤1~6,直到不能拆分子数列为止,整个数列就是一个从头开始递增的数列。

具体的代码实现如下:

<?php
class QuickSortClass{    public function partition(array &$arr, $startIndex, $endIndex)    {        // 取第一个元素为基准值        $pivot = $arr[$startIndex];        $left = $startIndex;        $right = $endIndex;
        // 坑的位置,出事等于基准值pivot的位置        $dataIndex = $startIndex;        while ($right >= $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]中。

本文分享自微信公众号 - 网管叨bi叨(kevin_tech),作者:KevinYan11

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二分查找算法速记

    二分查找(英语:binary search),也称折半搜索(英语:half-interval search)对数搜索(英语:logarithmic search...

    KevinYan
  • 关于JWT你要知道的都在这里

    失踪人口回归,之前因为换工作很多事情要处理断更了很长时间,最近在整理以前在Evernote里记的笔记,发现了以前记的JSON WEB TOKEN的东西,整理成文...

    KevinYan
  • Minikube-运行在笔记本上的Kubernetes集群

    Minikube是一个可以在本地电脑上运行Kubernetes的工具。Minikube会在笔记本电脑中的虚拟机上运行一个单节点的Kubernetes集群,让用户...

    KevinYan
  • 排序算法之快速排序

    快速排序是一种非常优秀的排序算法,应用的也非常广泛,面试时面试官也经常让你手写一个快排,所以说学习快速排序是非常有必要的。

    dejavu1zz
  • 数据结构 浅谈归并排序

    友情提示:此篇文章大约需要阅读 8分钟33秒,不足之处请多指教,感谢你的阅读。订阅本站

    Debug客栈
  • 阮一峰快速排序

    本打算学一波快速排序,查了查资料,吓一大跳,说阮一峰大神的快排是不对的,以此开始了一大波大神针对这个问题的各种观点。感兴趣的可以看看知乎这篇帖子:

    wade
  • 数据结构与算法 基础排序(O(n^2))

    不能直接找到一个比minIndex小的就swap,因为交换后比较的就是minIndex和后一个元素2个元素的比较 而不是minIndex和后面所有元素比较

    g小志
  • 算法之常见排序算法-冒泡排序、归并排序、快速排序

    对于编程中琳琅满目的算法,本人向来是不善此道也不精于此的,而说起排序算法,也只是会冒泡排序。还记得当初刚做开发工作面试第一家公司时,面试官便让手写冒泡排序(入职...

    本人秃顶程序员
  • Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋
  • 前端排序算法实现

    前端迷

扫码关注云+社区

领取腾讯云代金券