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

資訊專(zhuān)欄INFORMATION COLUMN

程序猿修仙之路--算法之快速排序到底有多快

trigkit4 / 1323人閱讀

摘要:可見(jiàn)快速排序不是穩(wěn)定的排序。在這種小數(shù)組的情況下,其實(shí)一些基礎(chǔ)排序算法反而比快速排序要快。當(dāng)一個(gè)數(shù)組為無(wú)序并且重復(fù)元素不多時(shí)候,也適合快速排序。

分治思想
關(guān)于排序,江湖盛傳有一種分治思想,能大幅度提高排序心法的性能。所謂分治,即:化大為小,分而治之。達(dá)到治小而治大的成效。多年來(lái)基于分治思想衍生出多種排序心法,然萬(wàn)變不離其宗!

雖然江湖上算法內(nèi)功繁多,但是好的算法小編認(rèn)為必須符合以下幾個(gè)條件,方能真正提高習(xí)練者實(shí)力。

時(shí)間復(fù)雜度(運(yùn)行時(shí)間)

在算法時(shí)間復(fù)雜度維度,我們主要對(duì)比較和交換的次數(shù)做對(duì)比,其他不交換元素的算法,主要會(huì)以訪問(wèn)數(shù)組的次數(shù)的維度做對(duì)比。

其實(shí)有很多修煉者對(duì)于算法的時(shí)間復(fù)雜度有點(diǎn)模糊,分不清什么所謂的 O(n),O(nlogn),O(logn)...等,也許下圖對(duì)一些人有一些更直觀的認(rèn)識(shí)。

空間復(fù)雜度(額外的內(nèi)存使用)

排序算法的額外內(nèi)存開(kāi)銷(xiāo)和運(yùn)行時(shí)間同等重要。 就算一個(gè)算法時(shí)間復(fù)雜度比較優(yōu)秀,空間復(fù)雜度非常差,使用的額外內(nèi)存非常大,菜菜認(rèn)為它也算不上一個(gè)優(yōu)秀的算法。

結(jié)果的正確性

這個(gè)指標(biāo)是菜菜自己加上的,我始終認(rèn)為一個(gè)優(yōu)秀的算法最終得到的結(jié)果必須是正確的。就算一個(gè)算法擁有非常優(yōu)秀的時(shí)間和空間復(fù)雜度,但是結(jié)果不正確,導(dǎo)致修煉者經(jīng)脈逆轉(zhuǎn),走火入魔,又有什么意義呢?
原理
基本思想:選取一個(gè)元素作為分割點(diǎn),通過(guò)遍歷把小于分割點(diǎn)的元素放到分割點(diǎn)左邊,把大于分割點(diǎn)的元素放到分割點(diǎn)元素右邊。然后再按此方法對(duì)兩部分?jǐn)?shù)據(jù)分別排序,以此類(lèi)推,直到分割的數(shù)組大小為1。 整個(gè)排序過(guò)程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
過(guò)程

實(shí)現(xiàn)快速排序的方式有很多,其中以類(lèi)似指針移動(dòng)方式最為常見(jiàn),為什么最常見(jiàn)呢?因?yàn)樗目臻g復(fù)雜度為O(1),也就是說(shuō)是原地排序。

我們從待排序的記錄序列中選取一個(gè)記錄(通常第一個(gè))作為基準(zhǔn)元素(稱(chēng)為key)key=arr[left],然后設(shè)置兩個(gè)變量,left指向數(shù)列的最左部,right指向數(shù)據(jù)的最右部。

key首先與arr[right]進(jìn)行比較,如果arr[right]key則我們只需要將right--,right--之后,再拿arr[right]與key進(jìn)行比較,直到arr[right]

如果右邊存在arr[right]key,則將arr[right]=arr[left],如果arr[left]

然后再移動(dòng)right重復(fù)上述步驟

最后得到 {23 58 13 10 57 62} 65 {106 78 95 85},再對(duì)左子數(shù)列與右子數(shù)列進(jìn)行同樣的操作。最終得到一個(gè)有序的數(shù)列。

{23 58 13 10 57 62} 65 {106 78   95 85}
{10 13} 23 {58 57 62} 65 {85 78 95} 106
10 13 23 57 58 62 65 78 85 95 106
性能特點(diǎn)
關(guān)于復(fù)雜度相關(guān)O(n)等公式,我這里需要強(qiáng)調(diào)一點(diǎn),公式代表的是算法的復(fù)雜度增長(zhǎng)的趨勢(shì),而不是具體計(jì)算復(fù)雜度的公式。比如:O(n2)和O(n)相比較,只是說(shuō)明 O(n2)增長(zhǎng)的趨勢(shì)要比o(n)快,并不是說(shuō)明O(n2)的算法比O(n)的算法所用時(shí)間一定就要多。
時(shí)間復(fù)雜度

快速排序平均時(shí)間復(fù)雜度為O(nlogn),最好情況下為O(nlogn),最壞情況下O(n2)

空間復(fù)雜度

基于以上例子來(lái)實(shí)現(xiàn)的快排,空間復(fù)雜度為O(1),也就是原地排序。

穩(wěn)定性

舉個(gè)例子:
待排序數(shù)組:int a[] ={1, 2, 2, 3, 4, 5, 6};

在快速排序的隨機(jī)選擇比較子(即pivot)階段:
若選擇a[2](即數(shù)組中的第二個(gè)2)為比較子,,而把大于等于比較子的數(shù)均放置在大數(shù)數(shù)組中,則a[1](即數(shù)組中的第一個(gè)2)會(huì)到pivot的右邊, 那么數(shù)組中的兩個(gè)2非原序(這就是“不穩(wěn)定”)。
若選擇a[1]為比較子,而把小于等于比較子的數(shù)均放置在小數(shù)數(shù)組中,則數(shù)組中的兩個(gè)2順序也非原序。可見(jiàn)快速排序不是穩(wěn)定的排序。

改進(jìn)

通過(guò)以上分析各位俠士是否能夠分析出來(lái)快速排序有哪些地方存在瑕疵呢?

切分不平衡:也就是說(shuō)我們選取的切分元素距離數(shù)組中間值的元素位置很遠(yuǎn),極端情況下會(huì)是數(shù)組最大或最小的元素,這就導(dǎo)致了劃分出來(lái)的大數(shù)組會(huì)被劃分為很多次。針對(duì)此情況,我們可以取數(shù)組多個(gè)元素來(lái)平衡這種情況,例如:我們可以隨機(jī)選取三個(gè)或者五個(gè)元素,取其中間值的元素作為分割元素。

小數(shù)組:當(dāng)快速排序切分為比較小的數(shù)組時(shí)候,也會(huì)利用遞歸調(diào)用自己。在這種小數(shù)組的情況下,其實(shí)一些基礎(chǔ)排序算法反而比快速排序要快。當(dāng)數(shù)組比較小的時(shí)候不妨嘗試一下切換到插入排序。具體多小是小呢?一般5-15吧,僅供參考。

重復(fù)元素:在我們實(shí)際應(yīng)用中經(jīng)常會(huì)遇到重復(fù)元素比較多的情況,按照快排的思想,相同元素是會(huì)被頻繁移動(dòng)和劃分的,其實(shí)這完全沒(méi)有必要。我們?cè)撛趺崔k呢?我們可以把數(shù)組切換為三部分:大于-等于-小于 三部分?jǐn)?shù)組,這樣等于的那部分?jǐn)?shù)組就可以避免移動(dòng)了,不過(guò)落地的代碼復(fù)雜度要高很多,有興趣的同學(xué)可以實(shí)現(xiàn)一下。

使用場(chǎng)景

當(dāng)一個(gè)數(shù)組大小為中型以上的數(shù)量級(jí)時(shí),菜菜認(rèn)為可以使用快速排序,并且伴隨著數(shù)組的持續(xù)增大,快速排序的性能趨于平均運(yùn)行時(shí)間。至于多大的數(shù)組為中型,一般認(rèn)為50+ 吧,僅供參考。

當(dāng)一個(gè)數(shù)組為無(wú)序并且重復(fù)元素不多時(shí)候,也適合快速排序。為什么提出重復(fù)元素這個(gè)點(diǎn)呢?因?yàn)槿绻貜?fù)元素過(guò)多,本來(lái)重復(fù)元素是無(wú)需排序的,但是快速排序還是要?jiǎng)澐譃楦嗟淖訑?shù)組來(lái)比較,這個(gè)時(shí)候也許插入排序更適合。

試煉一發(fā)吧
c# 武器版
        static void Main(string[] args)
        {
            List data = new List();
            for (int i = 0; i < 11; i++)
            {

                data.Add(new Random(Guid.NewGuid().GetHashCode()).Next(1, 100));
            }
            //打印原始數(shù)組值
            Console.WriteLine($"原始數(shù)據(jù): {string.Join(",", data)}");
            quickSort(data, 0, data.Count - 1);
            //打印排序后的數(shù)組
            Console.WriteLine($"排序數(shù)據(jù): {string.Join(",", data)}");
            Console.Read();
        }
        public static void quickSort(List  source, int left, int right)
        {
            int pivot = 0;
            if (left < right)
            {
                pivot = partition(source, left, right);
                quickSort(source, left, pivot - 1);
                quickSort(source, pivot + 1, right);
            }
        }
        //對(duì)一個(gè)數(shù)組/列表按照第一個(gè)元素 分組排序,返回排序之后key所在的位置索引
        private static int partition(List source, int left, int right)
        {
            int key = source[left];
            while (left < right)
            {
                //從右邊篩選 大于選取的值的不動(dòng),小于key的交換位置
                while (left < right && source[right] >= key)
                {
                    right--;
                }
                source[left] = source[right];
                while (left < right && source[left] <= key)
                {
                    left++;
                }
                source[right] = source[left];
            }
            source[left] = key;
            return left;
        }
golang 武器版
package main

import (
    "fmt"
    "math/rand"
)

func main() {
    var data []int
    for i := 0; i < 10; i++ {
        data = append(data, rand.Intn(100))
    }
    fmt.Println(data)
    quickSort(data[:], 0, len(data)-1)
    fmt.Println(data)
}
func quickSort(source []int, left int, right int) {
    var pivot = 0
    if left < right {
        pivot = partition(source, left, right)                                        
        quickSort(source, left, pivot-1)
        quickSort(source, pivot+1, right)
    }
}

func partition(source []int, left int, right int) int {
    var key = source[left]
    for left < right {
        for left < right && source[right] >= key {
            right--
        }
        source[left] = source[right]
        for left < right && source[left] <= key {
            left++
        }
        source[right] = source[left]
    }
    source[left] = key
    return left
}

運(yùn)行結(jié)果:

[81 87 47 59 81 18 25 40 56 0]
[0 18 25 40 47 56 59 81 81 87]
添加關(guān)注,查看更精美版本,收獲更多精彩

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

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/74328.html

相關(guān)文章

  • 程序修仙--算法快速排序到底多快

    摘要:可見(jiàn)快速排序不是穩(wěn)定的排序。在這種小數(shù)組的情況下,其實(shí)一些基礎(chǔ)排序算法反而比快速排序要快。當(dāng)一個(gè)數(shù)組為無(wú)序并且重復(fù)元素不多時(shí)候,也適合快速排序。 分治思想 關(guān)于排序,江湖盛傳有一種分治思想,能大幅度提高排序心法的性能。所謂分治,即:化大為小,分而治之。達(dá)到治小而治大的成效。多年來(lái)基于分治思想衍生出多種排序心法,然萬(wàn)變不離其宗!雖然江湖上算法內(nèi)功繁多,但是好的算法小編認(rèn)為必須符合以下幾...

    felix0913 評(píng)論0 收藏0
  • 用 PHP 的方式實(shí)現(xiàn)的各類(lèi)算法合集

    摘要:數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱(chēng)為邏輯結(jié)構(gòu)。 項(xiàng)目地址 https://github.com/m9rco/algo... 每周最少一更,求出題,求虐待 At least once a week, ask for problems and abuse 簡(jiǎn)...

    Karrdy 評(píng)論0 收藏0
  • 用 PHP 的方式實(shí)現(xiàn)的各類(lèi)算法合集

    摘要:數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱(chēng)為邏輯結(jié)構(gòu)。 項(xiàng)目地址 https://github.com/m9rco/algo... 每周最少一更,求出題,求虐待 At least once a week, ask for problems and abuse 簡(jiǎn)...

    pakolagij 評(píng)論0 收藏0
  • 用 PHP 的方式實(shí)現(xiàn)的各類(lèi)算法合集

    摘要:數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱(chēng)為邏輯結(jié)構(gòu)。 項(xiàng)目地址 https://github.com/m9rco/algo... 每周最少一更,求出題,求虐待 At least once a week, ask for problems and abuse 簡(jiǎn)...

    leonardofed 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<