快速排序填坑口诀

栏目: 编程工具 · 发布时间: 5年前

内容简介:快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此在很多笔试面试中出现的几率很高。直接默写出快速排序还是有一定难度的,所以一定要弄清楚原理再去记忆而不是去硬背。快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-Conque)。

快速排序由于 排序 效率在同为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] 中。


以上所述就是小编给大家介绍的《快速排序填坑口诀》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

共享经济时代

共享经济时代

雷切尔·博茨曼、路·罗杰斯 / 唐朝文 / 上海交通大学出版社 / 2015-6-1 / 38

“共享经济”(sharing economy),也被称为“协同消费”(collaborative consumption),是在互联网上兴起的一种全新的商业模式。简单地说,消费者可以通过合作的方式来和他人共同享用产品和服务,而无需持有产品与服务的所有权。使用但不拥有,分享替代私有,即“我的就是你的”。 当下,全球经济正呈现出这样一种前所未有的趋势:消费者之间的分享、交换、借贷、租赁等共享经济......一起来看看 《共享经济时代》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

SHA 加密
SHA 加密

SHA 加密工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具