成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

快速排序算法圖解與PHP實(shí)現(xiàn)講解

shleyZ / 2050人閱讀

摘要：概述快速排序最初由東尼霍爾提出，是一種平均時(shí)間復(fù)雜度為，最差時(shí)間復(fù)雜度為的排序算法。測試算法效率與復(fù)雜度完全隨機(jī)序列排序結(jié)果以下面的方法分別生成元素個(gè)數(shù)為萬萬的完全隨機(jī)數(shù)組，并用快速排序算法對其排序。

概述

快速排序（QuickSort）最初由東尼·霍爾提出，是一種平均時(shí)間復(fù)雜度為，最差時(shí)間復(fù)雜度為的排序算法。這種排序法使用的策略是基于分治法，其排序步驟如wiki百科-快速排序所述：

步驟為：
1.從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），
2.重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
3.遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。


遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會把一個(gè)元素?cái)[到它最后的位置去。

用一張圖簡單地表現(xiàn)以上步驟（注：圖中v就是基準(zhǔn)元素）。

下面，我將談?wù)剬?shí)現(xiàn)這種算法的一種簡單的方式。

算法實(shí)現(xiàn)圖解 1. 算法步驟、變量和指針

選定序列最左端的元素v為基準(zhǔn)元素，指針i指向當(dāng)前待比較的元素e，指針j總是指向的最右端，l為序列的最左端，r為序列的最右端。

如果e ≥ v，就將e擺放在深黃色的>v區(qū)域；如果e < v，就將v擺放在淺黃色的

完成一次比較之后，指針i會向右移動一位，繼續(xù)比較下一個(gè)元素與基準(zhǔn)元素的大小。

2. “擺放”操作與指針移動 情形一：e ≥ v

元素e的位置不改變，自然并入≥v的區(qū)域。

指針i向右移動一位，指向下一個(gè)待比較元素e。

指針j不需要移動。

情形二：e < v

交換元素e與≥v區(qū)域的最左端的元素，即swap(i, j+1)。

指針i向右移動一位，指向下一個(gè)待比較元素e。

指針j向右移動一位，指向當(dāng)前 情形三：單輪排序結(jié)束

此時(shí)，如圖中的第一個(gè)序列，v在最左端，然后是交換基準(zhǔn)元素v與指針i所指元素，即swap(l, j)，將整個(gè)序列分割為接下來，再分別對 PHP實(shí)現(xiàn)的例子 

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

    /**
     * 遞歸地對序列分區(qū)排序
     *
     * @param $arr array 整個(gè)序列
     * @param $l int 待排序的序列左端
     * @param $r int 待排序的序列右端
     */
    private static function sortRecursion(&$arr,$l,$r) {
        if ($l >= $r) {
            return;
        }
        $p = self::partition($arr,$l,$r);
        //對基準(zhǔn)點(diǎn)左右區(qū)域遞歸調(diào)用排序算法
        self::sortRecursion($arr,$l,$p-1);
        self::sortRecursion($arr,$p+1,$r);
    }

    /**
     * 分區(qū)操作
     *
     * @param $arr array 整個(gè)序列
     * @param $l int 待排序的序列左端
     * @param $r int 待排序的序列右端
     * @return mixed 基準(zhǔn)點(diǎn)
     */
    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;
    }

    /**
     * 交換數(shù)組的兩個(gè)元素
     *
     * @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 類的結(jié)構(gòu)

sort()方法是供外部調(diào)用快速排序算法的入口。

partition()方法對序列分區(qū)排序，對應(yīng)步驟二。

sortRecursion()方法遞歸地調(diào)用排序方法，對應(yīng)步驟三。

swap()方法用于交換序列中的兩個(gè)元素。

測試算法效率與復(fù)雜度 完全隨機(jī)序列排序結(jié)果

以下面的方法分別生成元素個(gè)數(shù)為1萬、10萬的完全隨機(jī)數(shù)組，并用快速排序算法對其排序。

// 生成指定元素個(gè)數(shù)的隨機(jī)數(shù)組
public static function generateRandomArray($n) {
    $list = [];
    for ($i=0; $i<$n; $i++) {
        $list[$i] = rand();
    }
    return $list;
}

在我的計(jì)算機(jī)運(yùn)行程序，

當(dāng)數(shù)組元素個(gè)數(shù)為1萬時(shí)，排序時(shí)間為21.929025650024 ms

當(dāng)數(shù)組元素個(gè)數(shù)為10萬時(shí)，排序時(shí)間為286.66996955872 ms

元素個(gè)數(shù)變成原來的10倍，運(yùn)行時(shí)間不到原來的14倍，可見算法的復(fù)雜度是級別的。
但是，當(dāng)待排序的數(shù)組是近似順序排序的數(shù)組時(shí)，這個(gè)算法就會退化為算法。

近似順序序列排序結(jié)果 
/**
 * 生成近似順序排序的數(shù)組
 *
 * @param $n int 元素個(gè)數(shù)
 * @param $swapTimes int 交換次數(shù)
 * @return array 生成的數(shù)組
 */
public static function generateNearlyOrderedIntArray($n,$swapTimes) {
    $arr = [];
    for ($i=0; $i<$n; $i++) {
        $arr[] = $i;
    }
    //交換數(shù)組中的任意兩個(gè)元素
    for ($i=0; $i<$swapTimes; $i++) {
        $indexA = rand() % $n;
        $indexB = rand() % $n;
        $tmp = $arr[$indexA];
        $arr[$indexA] = $arr[$indexB];
        $arr[$indexB] = $tmp;
    }
    return $arr;
}

使用上面的方法生成元素個(gè)數(shù)為1萬和10萬的近似順序排序數(shù)組，測試結(jié)果：

1萬：444.75889205933 ms

10萬：52281.121969223 ms

由此結(jié)果可知：

近似順序序列的排序時(shí)間遠(yuǎn)遠(yuǎn)大于完全隨機(jī)序列。

1萬與10萬的運(yùn)行時(shí)間相差117倍。當(dāng)然，由于計(jì)算機(jī)性能不穩(wěn)定，程序每次的運(yùn)行結(jié)果都是不同的，但是1萬和10萬的差距一定是在100這個(gè)數(shù)量級左右的數(shù)字，也就是算法復(fù)雜度為級別。

快速排序算法退化

當(dāng)待排序的序列是近似順序排序時(shí)，因?yàn)樗惴ㄟx取的基準(zhǔn)點(diǎn)是最左端的點(diǎn)（很大概率是最小的值），所以分區(qū)的結(jié)果是左邊的總的迭代次數(shù)接近序列的長度n，如果序列的長度變?yōu)樵瓉淼?0倍，那么迭代的次數(shù)也變?yōu)樵瓉淼?0倍，而每輪排序的時(shí)間也是原來的10倍，所以總的排序時(shí)間是原來的100倍。

優(yōu)化算法和代碼

針對順序排序?qū)е碌乃惴〞r(shí)間復(fù)雜度上升的問題，一個(gè)很有效的辦法就是改進(jìn)基準(zhǔn)點(diǎn)的選取方法。如果基準(zhǔn)點(diǎn)是隨機(jī)選取的，就可以消除這個(gè)問題了。

private static function partition(&$arr,$l,$r) {
    //優(yōu)化1：從數(shù)組中隨機(jī)選擇一個(gè)數(shù)與最左端的數(shù)交換，達(dá)到隨機(jī)挑選的效果
    //這個(gè)優(yōu)化使得快速排序在應(yīng)對近似有序數(shù)組排序時(shí)，迭代次數(shù)更少，排序算法效率更高
    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萬的近似順序排序數(shù)組，排序時(shí)間：

1萬：21.579027175903 ms

10萬：274.99508857727 ms

可見，排序的時(shí)間復(fù)雜度又變回級別了。

總結(jié)

理解算法實(shí)現(xiàn)實(shí)現(xiàn)過程的關(guān)鍵：分區(qū)的方法，以及指針i和j是如何移動的。

近似順序序列導(dǎo)致算法從級別退化到級別，隨機(jī)挑選基準(zhǔn)點(diǎn)是解決方法。

這個(gè)算法還存在其他的問題，為了解決這些問題，衍生了諸如雙路排序和三路排序的快速排序算法，有空再寫寫單路排序算法的其他問題，并介紹那兩種改進(jìn)的算法。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/28356.html

相關(guān)文章

  • 算法之旅 | 快速排序法

    摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時(shí)間復(fù)雜度為?？焖倥判蚍ǖ脑砜焖倥判蚴且环N劃分交換排序，它采用分治的策略，通常稱其為分治法。 HTML5學(xué)堂-碼匠：前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法，它們都屬于時(shí)間復(fù)雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法—— 快速排序法 [ 平均時(shí)間復(fù)雜度為O (n l...

    AlanKeene 評論0 收藏0

  • 【算法】算法圖解筆記_算法簡介

    摘要：在本書中你將學(xué)習(xí)比較不同算法的優(yōu)缺點(diǎn)該使用合并排序算法還是快速排序算法或者該使用數(shù)組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。 在讀《算法圖解》這本書，這本書有兩個(gè)優(yōu)點(diǎn)： 手繪風(fēng)格的圖，看著很讓人入戲； 算法采用Python語言描述，能更好的表達(dá)算法思想。 關(guān)于算法的學(xué)習(xí)有兩點(diǎn)心得： 算法思想最重要，理解了思想，算法是很容易寫出來的，所以盡量不要把過多精力放在細(xì)節(jié)上...

    tomlingtm 評論0 收藏0

  • 【算法】算法圖解筆記_快速排序

    摘要：再談大表示法快速排序的獨(dú)特之處在于其速度取決于選擇的基準(zhǔn)值。在平均情況下快速排序的運(yùn)行時(shí)間為在最糟情況下退化為?？焖倥判蚝秃喜⑴判虻乃惴ㄋ俣确謩e表示為和，是算法所需的固定時(shí)間量被稱為常量。 分而治之 分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個(gè)可供你使用的工具。 D&C...

    YanceyOfficial 評論0 收藏0

  • 輕松讀懂?dāng)?shù)據(jù)結(jié)構(gòu)系列：早操排隊(duì)圖解冒泡排序

    摘要：二冒泡排序算法作為這一系列的第一部分，主要講解排序算法。直到隊(duì)列全部排好為止。到這里，我想你應(yīng)該明白了冒泡排序的思想了。 一、說在前面 一直想寫一些簡單易懂的文章，因?yàn)槠綍r(shí)看的很多的書籍或者文章都是看著很難受的感覺，當(dāng)然，這并不是說書籍寫的不好，只是說對于一些沒有太多基礎(chǔ)或者基礎(chǔ)不是很好的來說，相對來說還是比較難以理解的。 這個(gè)系列主要是寫一些簡單易懂的數(shù)據(jù)結(jié)構(gòu)與算法的文章，同時(shí)也是幫...

    Shisui 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<