數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之如何分析一個(gè)排序算法?

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之如何分析一個(gè)排序算法余佃?

前言

現(xiàn)在IT這塊找工作暮刃,不會(huì)幾個(gè)算法都不好意思出門,排序算法恰巧是其中最簡(jiǎn)單的爆土,我接觸的第一個(gè)算法就是它椭懊,但是你知道怎么分析一個(gè)排序算法么?有很多時(shí)間復(fù)雜度相同的排序算法步势,在實(shí)際編碼中氧猬,那又如何選擇呢?下面我們帶著問題一起學(xué)習(xí)一下坏瘩。

正文

一盅抚、常見經(jīng)典的排序方法

(圖片來自于一像素

插入排序

image

希爾排序(遞減增量排序算法)

image

歸并排序

image

快速排序

image

冒泡排序

image

選擇排序

image

計(jì)數(shù)排序

image

計(jì)數(shù)排序

image

堆排序

image

二、 按照時(shí)間復(fù)雜度歸類

時(shí)間復(fù)雜度O(n2):

冒泡排序倔矾、插入排序妄均、選擇排序

時(shí)間復(fù)雜度O(nlogn):
快速排序柱锹、歸并排序

時(shí)間復(fù)雜度O(n):

計(jì)數(shù)排序、基數(shù)排序丰包、桶排序

三禁熏、如何分析一個(gè)“排序算法”?

從三個(gè)方面入手

a邑彪、算法的執(zhí)行效率

1.最好瞧毙、最壞、平均情況時(shí)間復(fù)雜度寄症。

從算法的核心宙彪,復(fù)雜度入手,給出最好最壞有巧,平均情況下的時(shí)間復(fù)雜度释漆,便于分析

  1. 時(shí)間復(fù)雜度的系數(shù)、常數(shù)和低階剪决。

時(shí)間復(fù)雜度表示的是規(guī)模很大的一種增漲趨勢(shì)灵汪,很容易就忽略系數(shù),低階柑潦,常數(shù)等,實(shí)際開發(fā)中排序的規(guī)模都是像10.100.1000這種小規(guī)模

  1. 比較次數(shù)峻凫,交換(或移動(dòng))次數(shù)渗鬼。

排序算法執(zhí)行過程中,涉及兩種操作荧琼,一種是元素比較大小譬胎,一種是元素交換或移動(dòng)位置,所以比較次數(shù)命锄,交換次數(shù)都得考慮進(jìn)去堰乔。

b、排序算法的內(nèi)存消耗

算法消耗可以通過空間復(fù)雜度來衡量

原地排序算法:特指空間復(fù)雜度是O(1)的排序算法脐恩。

c镐侯、排序算法的穩(wěn)定性

  1. 穩(wěn)定性概念:如果待排序的序列中存在值相等的元素,經(jīng)過排序之后驶冒,相等元素之間原有的先后順序不變苟翻。
  2. 穩(wěn)定性重要性:可針對(duì)對(duì)象的多種屬性進(jìn)行有優(yōu)先級(jí)的排序。
  3. 舉例:給電商交易系統(tǒng)中的“訂單”排序骗污,按照金額大小對(duì)訂單數(shù)據(jù)排序崇猫,對(duì)于相同金額的訂單以下單時(shí)間早晚排序。用穩(wěn)定排序算法可簡(jiǎn)潔地解決需忿。先按照下單時(shí)間給訂單排序诅炉,排序完成后用穩(wěn)定排序算法按照訂單金額重新排序蜡歹。

四、詳解冒泡排序

冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)涕烧。每次冒泡操作都會(huì)對(duì)相鄰的兩個(gè)元素進(jìn)行比較月而,看是否滿足大小關(guān)系要求,如果不滿足就讓它倆互換澈魄。

冒泡排序只涉及相鄰數(shù)據(jù)的交換景鼠,只需要常量級(jí)的臨時(shí)空間,所以它的空間復(fù)雜度未O(1)是原地排序算法

穩(wěn)定性:當(dāng)有相鄰的兩個(gè)元素大小相等時(shí)痹扇,不做交換铛漓,冒泡排序是穩(wěn)定的排序算法。

引入兩個(gè)概念:

默認(rèn)從小到大未有序

有序度:數(shù)組中具有有序關(guān)系的元素對(duì)的個(gè)數(shù)鲫构。

滿有序度:完全有序的數(shù)組

逆序度:數(shù)組中具有無序關(guān)系的元素對(duì)的個(gè)數(shù)浓恶。

逆序度=滿有序度-有序度

排序的過程實(shí)際上就是增加有序度,減少逆序度的過程

時(shí)間復(fù)雜度:

  1. 最好情況(滿有序度):O(n)结笨。
  2. 最壞情況(滿逆序度):O(n^2)包晰。
  3. 平均情況:
    “有序度”和“逆序度”:對(duì)于一個(gè)不完全有序的數(shù)組,如4炕吸,5伐憾,6,3赫模,2树肃,1,有序元素對(duì)為3個(gè)(4瀑罗,5)胸嘴,(4,6)斩祭,(5劣像,6),有序度為3摧玫,逆序度為12耳奕;對(duì)于一個(gè)完全有序的數(shù)組,如1席赂,2吮铭,3,4颅停,5谓晌,6,有序度就是n(n-1)/2癞揉,也就是15纸肉,稱作滿有序度溺欧;逆序度=滿有序度-有序度;冒泡排序柏肪、插入排序交換(或移動(dòng))次數(shù)=逆序度姐刁。
    最好情況下初始有序度為n
    (n-1)/2,最壞情況下初始有序度為0烦味,則平均初始有序度為n(n-1)/4聂使,即交換次數(shù)為n(n-1)/4,因交換次數(shù)<比較次數(shù)<最壞情況時(shí)間復(fù)雜度谬俄,所以平均時(shí)間復(fù)雜度為O(n2)柏靶。

代碼實(shí)現(xiàn):

<pre style="margin: 0px 0px 15px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px !important; line-height: 1.72222; color: inherit; border-radius: 2px; background: rgb(238, 238, 238); border: 0px; overflow: auto;">// 冒泡排序,a 表示數(shù)組溃论,n 表示數(shù)組大小
public void bubbleSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n; ++i) { // 提前退出冒泡循環(huán)的標(biāo)志位
boolean flag = false; for (int j = 0; j < n - i - 1; ++j) { if (a[j] > a[j+1]) { // 交換
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有數(shù)據(jù)交換
}
} if (!flag) break; // 沒有數(shù)據(jù)交換屎蜓,提前退出
}
}</pre>

五、詳解插入排序

將數(shù)據(jù)分為兩個(gè)區(qū)間钥勋,已排序區(qū)間和未排序區(qū)間炬转,初始已排序區(qū)間只有一個(gè)元素(即第一個(gè)數(shù)據(jù)),我們?nèi)∥磁判騾^(qū)間的元素算灸,在已排序的區(qū)間中找到合適的位置插入位置插入扼劈,并保證已排序區(qū)間數(shù)據(jù)一直有序,重復(fù)過程菲驴,直到未排序區(qū)間中沒有元素

運(yùn)行過程中看得出來测僵,不需要額外的存儲(chǔ)空間,所以空間復(fù)雜度為0(1)谢翎,也是原地排序算法

同樣值的元素,前后順序保持不變沐旨,是穩(wěn)定的排序算法

時(shí)間復(fù)雜度:

最好時(shí)間復(fù)雜度為O(n)

最壞時(shí)間復(fù)雜度為O(n2)

平均時(shí)間復(fù)雜度為O(n2)

代碼實(shí)現(xiàn):

<pre style="margin: 0px 0px 15px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px !important; line-height: 1.72222; color: inherit; border-radius: 2px; background: rgb(238, 238, 238); border: 0px; overflow: auto;">// 插入排序森逮,a 表示數(shù)組,n 表示數(shù)組大小
public void insertionSort(int[] a, int n) { if (n <= 1) return; for (int i = 1; i < n; ++i) { int value = a[i]; int j = i - 1; // 查找插入的位置
for (; j >= 0; --j) { if (a[j] > value) {
a[j+1] = a[j]; // 數(shù)據(jù)移動(dòng)
} else { break;
}
}
a[j+1] = value; // 插入數(shù)據(jù)
}
}</pre>

六磁携、詳解選擇排序

選擇排序?qū)?shù)組數(shù)據(jù)分成已排序區(qū)間和未排序區(qū)間褒侧。初始已排序區(qū)間只有一個(gè)元素,即數(shù)組第一個(gè)元素谊迄。在未排序區(qū)間找到最小的數(shù)據(jù)闷供,將其放在已排序區(qū)間的末尾

空間復(fù)雜度為O(1),選擇排序是原地排序算法统诺。

未排序區(qū)間的元素和已排序區(qū)間的元素相同時(shí)歪脏,它可以放在已排序區(qū)間相同值的前或后,所以為不穩(wěn)定的排序

時(shí)間復(fù)雜度:

  1. 最好情況:O(n2)粮呢。
  2. 最壞情況:O(n2)婿失。
  3. 平均情況:O(n2)(往數(shù)組中插入一個(gè)數(shù)的平均時(shí)間復(fù)雜度是O(n)钞艇,一共重復(fù)n次)。

七豪硅、各種排序方法的匯總比較

image

八哩照、選擇排序和插入排序的時(shí)間復(fù)雜度相同,都是O(n^2)懒浮,在實(shí)際的軟件開發(fā)中飘弧,為什么我們更傾向于使用插入排序而不是冒泡排序算法呢?

答:它們的元素比較次數(shù)以及交換元素的次數(shù)都是原始數(shù)據(jù)的逆序度砚著,是一個(gè)固定值次伶,但是從代碼實(shí)現(xiàn)上來看,冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動(dòng)要復(fù)雜赖草,冒泡排序需要3個(gè)賦值操作学少,而插入排序只需要1個(gè),他們 的時(shí)間復(fù)雜度上都是O(n2)秧骑,但是為了追求極致的性能版确,所以首選插入排序算法

結(jié)尾

大家不妨試著分析一下其他的幾種算法。

看再多遍都不如寫一篇來得深刻乎折,建議大家多敲绒疗。

相關(guān)文章

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之寫鏈表代碼的正確姿勢(shì)(下)

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之 提高讀取性能的鏈表(上)

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之 從0編號(hào)的數(shù)組

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之后進(jìn)先出的“桶”

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之先進(jìn)先出的隊(duì)列

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之高效、簡(jiǎn)潔的編碼技巧“遞歸”

以上內(nèi)容為個(gè)人的學(xué)習(xí)筆記骂澄,僅作為學(xué)習(xí)交流之用吓蘑。

Dawnzhang公眾號(hào).jpg

歡迎大家關(guān)注公眾號(hào),不定時(shí)干貨坟冲,只做有價(jià)值的輸出

作者:Dawnzhang
出處:https://www.cnblogs.com/clwydjgs/p/9815690.html

小舟從此逝磨镶,江海寄余生。 --狐貍

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末健提,一起剝皮案震驚了整個(gè)濱河市琳猫,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌私痹,老刑警劉巖脐嫂,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異紊遵,居然都是意外死亡账千,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門暗膜,熙熙樓的掌柜王于貴愁眉苦臉地迎上來匀奏,“玉大人,你說我怎么就攤上這事桦山≡苌洌” “怎么了醋旦?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)会放。 經(jīng)常有香客問我饲齐,道長(zhǎng),這世上最難降的妖魔是什么咧最? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任捂人,我火速辦了婚禮,結(jié)果婚禮上矢沿,老公的妹妹穿的比我還像新娘滥搭。我一直安慰自己,他們只是感情好捣鲸,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布瑟匆。 她就那樣靜靜地躺著,像睡著了一般栽惶。 火紅的嫁衣襯著肌膚如雪愁溜。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天外厂,我揣著相機(jī)與錄音冕象,去河邊找鬼。 笑死汁蝶,一個(gè)胖子當(dāng)著我的面吹牛渐扮,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播掖棉,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼墓律,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了幔亥?” 一聲冷哼從身側(cè)響起只锻,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎紫谷,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體捐寥,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡笤昨,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了握恳。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片瞒窒。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖乡洼,靈堂內(nèi)的尸體忽然破棺而出崇裁,到底是詐尸還是另有隱情匕坯,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布拔稳,位于F島的核電站葛峻,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏巴比。R本人自食惡果不足惜术奖,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望轻绞。 院中可真熱鬧采记,春花似錦、人聲如沸政勃。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)奸远。三九已至既棺,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間然走,已是汗流浹背援制。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留芍瑞,地道東北人晨仑。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像拆檬,于是被迫代替她去往敵國(guó)和親洪己。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 概述 排序有內(nèi)部排序和外部排序竟贯,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序答捕,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部...
    蟻前閱讀 5,191評(píng)論 0 52
  • 概述:排序有內(nèi)部排序和外部排序屑那,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序拱镐,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部...
    每天刷兩次牙閱讀 3,733評(píng)論 0 15
  • 江面是我崩塌的冰川 布滿破碎的冰凌持际,在夜里反光 你的手指在風(fēng)中撥動(dòng) 橋墩隨你的指揮沃琅,忽暗忽明 我是你的船底 在暗礁...
    霧西L閱讀 162評(píng)論 0 6
  • 文 | 陳葉子 有一部國(guó)產(chǎn)片,讓我看后為其感到驕傲蜘欲,《戰(zhàn)狼2》做到了益眉。因?yàn)槲覀儾皇巧钤诤推綍r(shí)代,而是生活在和平的...
    chenyezizjnu閱讀 318評(píng)論 0 4
  • 每次電視或是其他什么地方當(dāng)故鄉(xiāng)兩個(gè)字出現(xiàn)的時(shí)候,我總是沒有什么感覺郭脂,覺得這兩個(gè)字和我沒有什么關(guān)系年碘,畢竟我對(duì)故鄉(xiāng)那七...
    蕓小逗閱讀 212評(píng)論 0 0