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

Trista 发布于6月前 阅读73次
0 条评论

概述

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

步骤为:

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

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

用一张图简单地表现以上步骤(注:图中v就是基准元素)。

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

算法实现图解

1. 算法步骤、变量和指针

  1. 选定序列最左端的元素v为基准元素,指针i指向当前待比较的元素e指针j总是指向<v区域的最右端,l为序列的最左端,r为序列的最右端。
  2. 如果e ≥ v,就将e摆放在深黄色的>v区域;如果e < v,就将v摆放在浅黄色的<v区域。“摆放”操作的详细方法会在下面解说。
  3. 完成一次比较之后,指针i会向右移动一位,继续比较下一个元素与基准元素的大小。

2. “摆放”操作与指针移动

情形一:e ≥ v

  • 元素e的位置不改变,自然并入≥v的区域。
  • 指针i向右移动一位,指向下一个待比较元素e。
  • 指针j不需要移动。

情形二:e < v

  • 交换元素e与≥v区域的最左端的元素,即swap(i, j+1)。<v区域扩充到j+1,≥v区域总体不变(但是首元素与末元素调换了位置)。
  • 指针i向右移动一位,指向下一个待比较元素e。
  • 指针j向右移动一位,指向当前<v区域的最右端。

情形三:单轮排序结束

此时,如图中的第一个序列,v在最左端,然后是<v的区域和≥v的区域,指针j指向<v区域的最右端,指针i指向序列的最左端。
交换基准元素v与指针i所指元素,即swap(l, j),将整个序列分割为<v和≥v两个区域,如图中的第二个序列。
接下来,再分别对<v和≥v两个序列进行下一轮排序,以此类推,直至后代序列只剩下一个元素,整个序列的排序完毕了。

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这个数量级左右的数字,也就是算法复杂度为级别。

快速排序算法退化

当待排序的序列是近似顺序排序时,因为算法选取的基准点是最左端的点(很大概率是最小的值),所以分区的结果是左边的<v区域很短或者没有,右边的≥v区域很长,总的迭代次数接近序列的长度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是如何移动的。
  • 近似顺序序列导致算法从级别退化到级别,随机挑选基准点是解决方法。
  • 这个算法还存在其他的问题,为了解决这些问题,衍生了诸如双路排序和三路排序的快速排序算法,有空再写写单路排序算法的其他问题,并介绍那两种改进的算法。

查看原文: 快速排序算法图解与PHP实现讲解

  • organicladybug
  • silvercat
  • purplekoala
  • whitepanda
  • lazyostrich
  • heavymouse
需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。