亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

shleyZ / 2107人閱讀

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

概述

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

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


遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個算法一定會結(jié)束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

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

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

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

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

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

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

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

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

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

指針j不需要移動。

情形二：e < v

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

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

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

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

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

    /**
     * 遞歸地對序列分區(qū)排序
     *
     * @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);
        //對基準點左右區(qū)域遞歸調(diào)用排序算法
        self::sortRecursion($arr,$l,$p-1);
        self::sortRecursion($arr,$p+1,$r);
    }

    /**
     * 分區(qū)操作
     *
     * @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;
    }

    /**
     * 交換數(shù)組的兩個元素
     *
     * @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()方法用于交換序列中的兩個元素。

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

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

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

在我的計算機運行程序，

當數(shù)組元素個數(shù)為1萬時，排序時間為21.929025650024 ms

當數(shù)組元素個數(shù)為10萬時，排序時間為286.66996955872 ms

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

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

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

1萬：444.75889205933 ms

10萬：52281.121969223 ms

由此結(jié)果可知：

近似順序序列的排序時間遠遠大于完全隨機序列。

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

快速排序算法退化

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

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

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

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

1萬：21.579027175903 ms

10萬：274.99508857727 ms

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

總結(jié)

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

近似順序序列導致算法從級別退化到級別，隨機挑選基準點是解決方法。

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

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

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

相關(guān)文章

  • 算法之旅 | 快速排序法

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

    AlanKeene 評論0 收藏0

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

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

    tomlingtm 評論0 收藏0

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

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

    YanceyOfficial 評論0 收藏0

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

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

    Shisui 評論0 收藏0

發(fā)表評論

0條評論

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