国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

快速排序算法圖解與PHP實現講解

shleyZ / 2021人閱讀

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

概述

快速排序（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是如何移動的。

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

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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元查看
<