资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/快速排序算法图解与PHP实现讲解

快速排序算法图解与PHP实现讲解

shleyZ / 1997人阅读

摘要：概述快速排序最初由东尼霍尔提出，是一种平均时间复杂度为，最差时间复杂度为的排序算法。测试算法效率与复杂度完全随机序列排序结果以下面的方法分别生成元素个数为万万的完全随机数组，并用快速排序算法对其排序。

概述

快速排序（QuickSort）最初由东尼·霍尔提出，是一种平均时间复杂度为，最差时间复杂度为的排序算法。这种排序法使用的策略是基于分治法，其排序步骤如wiki百科-快速排序所述：

步骤为：
1.从数列中挑出一个元素，称为"基准"（pivot），
2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。


递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

用一张图简单地表现以上步骤（注：图中v就是基准元素）。

下面，我将谈谈实现这种算法的一种简单的方式。

算法实现图解 1. 算法步骤、变量和指针

选定序列最左端的元素v为基准元素，指针i指向当前待比较的元素e，指针j总是指向的最右端，l为序列的最左端，r为序列的最右端。

如果e ≥ v，就将e摆放在深黄色的>v区域；如果e < v，就将v摆放在浅黄色的

完成一次比较之后，指针i会向右移动一位，继续比较下一个元素与基准元素的大小。

2. “摆放”操作与指针移动 情形一：e ≥ v

元素e的位置不改变，自然并入≥v的区域。

指针i向右移动一位，指向下一个待比较元素e。

指针j不需要移动。

情形二：e < v

交换元素e与≥v区域的最左端的元素，即swap(i, j+1)。

指针i向右移动一位，指向下一个待比较元素e。

指针j向右移动一位，指向当前 情形三：单轮排序结束

此时，如图中的第一个序列，v在最左端，然后是交换基准元素v与指针i所指元素，即swap(l, j)，将整个序列分割为接下来，再分别对 PHP实现的例子 

class QuickSort
{
    /**
     * 外部调用快速排序的方法
     *
     * @param $arr array 整个序列
     */
    public static function sort(&$arr) {
        $length = count($arr);
        self::sortRecursion($arr,0,$length-1);
    }

    /**
     * 递归地对序列分区排序
     *
     * @param $arr array 整个序列
     * @param $l int 待排序的序列左端
     * @param $r int 待排序的序列右端
     */
    private static function sortRecursion(&$arr,$l,$r) {
        if ($l >= $r) {
            return;
        }
        $p = self::partition($arr,$l,$r);
        //对基准点左右区域递归调用排序算法
        self::sortRecursion($arr,$l,$p-1);
        self::sortRecursion($arr,$p+1,$r);
    }

    /**
     * 分区操作
     *
     * @param $arr array 整个序列
     * @param $l int 待排序的序列左端
     * @param $r int 待排序的序列右端
     * @return mixed 基准点
     */
    private static function partition(&$arr,$l,$r) {
        $v = $arr[$l];
        $j = $l;
        for ($i=$l+1; $i<=$r; $i++) {
            if ($arr[$i] < $v) {
                $j++;
                self::swap($arr,$i,$j);
            }
        }
        self::swap($arr,$l,$j);
        return $j;
    }

    /**
     * 交换数组的两个元素
     *
     * @param $arr array
     * @param $i int
     * @param $j int
     */
    private static function swap(&$arr,$i, $j) {
        $tmp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $tmp;
    }
}
QuickSort 类的结构

sort()方法是供外部调用快速排序算法的入口。

partition()方法对序列分区排序，对应步骤二。

sortRecursion()方法递归地调用排序方法，对应步骤三。

swap()方法用于交换序列中的两个元素。

测试算法效率与复杂度 完全随机序列排序结果

以下面的方法分别生成元素个数为1万、10万的完全随机数组，并用快速排序算法对其排序。

// 生成指定元素个数的随机数组
public static function generateRandomArray($n) {
    $list = [];
    for ($i=0; $i<$n; $i++) {
        $list[$i] = rand();
    }
    return $list;
}

在我的计算机运行程序，

当数组元素个数为1万时，排序时间为21.929025650024 ms

当数组元素个数为10万时，排序时间为286.66996955872 ms

元素个数变成原来的10倍，运行时间不到原来的14倍，可见算法的复杂度是级别的。
但是，当待排序的数组是近似顺序排序的数组时，这个算法就会退化为算法。

近似顺序序列排序结果 
/**
 * 生成近似顺序排序的数组
 *
 * @param $n int 元素个数
 * @param $swapTimes int 交换次数
 * @return array 生成的数组
 */
public static function generateNearlyOrderedIntArray($n,$swapTimes) {
    $arr = [];
    for ($i=0; $i<$n; $i++) {
        $arr[] = $i;
    }
    //交换数组中的任意两个元素
    for ($i=0; $i<$swapTimes; $i++) {
        $indexA = rand() % $n;
        $indexB = rand() % $n;
        $tmp = $arr[$indexA];
        $arr[$indexA] = $arr[$indexB];
        $arr[$indexB] = $tmp;
    }
    return $arr;
}

使用上面的方法生成元素个数为1万和10万的近似顺序排序数组，测试结果：

1万：444.75889205933 ms

10万：52281.121969223 ms

由此结果可知：

近似顺序序列的排序时间远远大于完全随机序列。

1万与10万的运行时间相差117倍。当然，由于计算机性能不稳定，程序每次的运行结果都是不同的，但是1万和10万的差距一定是在100这个数量级左右的数字，也就是算法复杂度为级别。

快速排序算法退化

当待排序的序列是近似顺序排序时，因为算法选取的基准点是最左端的点（很大概率是最小的值），所以分区的结果是左边的总的迭代次数接近序列的长度n，如果序列的长度变为原来的10倍，那么迭代的次数也变为原来的10倍，而每轮排序的时间也是原来的10倍，所以总的排序时间是原来的100倍。

优化算法和代码

针对顺序排序导致的算法时间复杂度上升的问题，一个很有效的办法就是改进基准点的选取方法。如果基准点是随机选取的，就可以消除这个问题了。

private static function partition(&$arr,$l,$r) {
    //优化1：从数组中随机选择一个数与最左端的数交换，达到随机挑选的效果
    //这个优化使得快速排序在应对近似有序数组排序时，迭代次数更少，排序算法效率更高
    self::swap($arr,$l,rand($l+1,$r));
    
    $v = $arr[$l];
    $j = $l;
    for ($i=$l+1; $i<=$r; $i++) {
        if ($arr[$i] < $v) {
            $j++;
            self::swap($arr,$i,$j);
        }
    }
    self::swap($arr,$l,$j);
    return $j;
}

依然是1万和10万的近似顺序排序数组，排序时间：

1万：21.579027175903 ms

10万：274.99508857727 ms

可见，排序的时间复杂度又变回级别了。

总结

理解算法实现实现过程的关键：分区的方法，以及指针i和j是如何移动的。

近似顺序序列导致算法从级别退化到级别，随机挑选基准点是解决方法。

这个算法还存在其他的问题，为了解决这些问题，衍生了诸如双路排序和三路排序的快速排序算法，有空再写写单路排序算法的其他问题，并介绍那两种改进的算法。

云服务器 GPU云服务器 排序算法图解 快速排序算法 最好的快速排序算法 最快速的排序算法

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

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

相关文章

  • 算法之旅 | 快速排序法

    摘要：今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法快速排序法平均时间复杂度为。快速排序法的原理快速排序是一种划分交换排序，它采用分治的策略，通常称其为分治法。 HTML5学堂-码匠：前几期算法之旅跟大家分享了冒泡排序法和选择排序法，它们都属于时间复杂度为O(n^2)的慢排序。今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法—— 快速排序法 [ 平均时间复杂度为O (n l...

    AlanKeene 评论0 收藏0

  • 【算法】算法图解笔记_算法简介

    摘要：在本书中你将学习比较不同算法的优缺点该使用合并排序算法还是快速排序算法或者该使用数组还是链表。这样的算法包括快速排序一种速度较快的排序算法。 在读《算法图解》这本书，这本书有两个优点： 手绘风格的图，看着很让人入戏； 算法采用Python语言描述，能更好的表达算法思想。 关于算法的学习有两点心得： 算法思想最重要，理解了思想，算法是很容易写出来的，所以尽量不要把过多精力放在细节上...

    tomlingtm 评论0 收藏0

  • 【算法】算法图解笔记_快速排序

    摘要：再谈大表示法快速排序的独特之处在于其速度取决于选择的基准值。在平均情况下快速排序的运行时间为在最糟情况下退化为。快速排序和合并排序的算法速度分别表示为和，是算法所需的固定时间量被称为常量。 分而治之 分而治之(divide and conquer,D&C)是一种著名的递归式问题解决方法。只能解决一种问题的算法毕竟用处有限,而D&C提供了解决问题的思路,是另一个可供你使用的工具。 D&C...

    YanceyOfficial 评论0 收藏0

  • 轻松读懂数据结构系列：早操排队图解冒泡排序

    摘要：二冒泡排序算法作为这一系列的第一部分，主要讲解排序算法。直到队列全部排好为止。到这里，我想你应该明白了冒泡排序的思想了。 一、说在前面 一直想写一些简单易懂的文章，因为平时看的很多的书籍或者文章都是看着很难受的感觉，当然，这并不是说书籍写的不好，只是说对于一些没有太多基础或者基础不是很好的来说，相对来说还是比较难以理解的。 这个系列主要是写一些简单易懂的数据结构与算法的文章，同时也是帮...

    Shisui 评论0 收藏0

发表评论

登陆后可评论

0条评论

shleyZ

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<