數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之如何分析一個(gè)排序算法余佃?
前言
現(xiàn)在IT這塊找工作暮刃,不會(huì)幾個(gè)算法都不好意思出門,排序算法恰巧是其中最簡(jiǎn)單的爆土,我接觸的第一個(gè)算法就是它椭懊,但是你知道怎么分析一個(gè)排序算法么?有很多時(shí)間復(fù)雜度相同的排序算法步势,在實(shí)際編碼中氧猬,那又如何選擇呢?下面我們帶著問題一起學(xué)習(xí)一下坏瘩。
正文
一盅抚、常見經(jīng)典的排序方法
(圖片來自于一像素)
插入排序
希爾排序(遞減增量排序算法)
歸并排序
快速排序
冒泡排序
選擇排序
計(jì)數(shù)排序
計(jì)數(shù)排序
堆排序
二、 按照時(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ù)雜度释漆,便于分析
- 時(shí)間復(fù)雜度的系數(shù)、常數(shù)和低階剪决。
時(shí)間復(fù)雜度表示的是規(guī)模很大的一種增漲趨勢(shì)灵汪,很容易就忽略系數(shù),低階柑潦,常數(shù)等,實(shí)際開發(fā)中排序的規(guī)模都是像10.100.1000這種小規(guī)模
- 比較次數(shù)峻凫,交換(或移動(dòng))次數(shù)渗鬼。
排序算法執(zhí)行過程中,涉及兩種操作荧琼,一種是元素比較大小譬胎,一種是元素交換或移動(dòng)位置,所以比較次數(shù)命锄,交換次數(shù)都得考慮進(jìn)去堰乔。
b、排序算法的內(nèi)存消耗
算法消耗可以通過空間復(fù)雜度來衡量
原地排序算法:特指空間復(fù)雜度是O(1)的排序算法脐恩。
c镐侯、排序算法的穩(wěn)定性
- 穩(wěn)定性概念:如果待排序的序列中存在值相等的元素,經(jīng)過排序之后驶冒,相等元素之間原有的先后順序不變苟翻。
- 穩(wěn)定性重要性:可針對(duì)對(duì)象的多種屬性進(jìn)行有優(yōu)先級(jí)的排序。
- 舉例:給電商交易系統(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ù)雜度:
- 最好情況(滿有序度):O(n)结笨。
- 最壞情況(滿逆序度):O(n^2)包晰。
- 平均情況:
“有序度”和“逆序度”:對(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ù)雜度:
- 最好情況:O(n2)粮呢。
- 最壞情況:O(n2)婿失。
- 平均情況:O(n2)(往數(shù)組中插入一個(gè)數(shù)的平均時(shí)間復(fù)雜度是O(n)钞艇,一共重復(fù)n次)。
七豪硅、各種排序方法的匯總比較
八哩照、選擇排序和插入排序的時(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í)交流之用吓蘑。
歡迎大家關(guān)注公眾號(hào),不定時(shí)干貨坟冲,只做有價(jià)值的輸出
作者:Dawnzhang
出處:https://www.cnblogs.com/clwydjgs/p/9815690.html
小舟從此逝磨镶,江海寄余生。 --狐貍