排序算法效率分析及總結(jié)

語言主流的排序算法效率剖析及總結(jié)班級(jí)：計(jì)科二班

作者：

XXX日期：2016-3-29

工作：算法收集及程序組合，結(jié)論總結(jié)。禮拜二

同組者：劉文工作：程序測試，時(shí)間記錄以及程序演示此次我們組主要收集了冒泡排序算法，簡單排序算法，直接插入排序算法，希爾排序算法，堆排序算法，迅速排序算法六種常有的排序算法，并對它們的運(yùn)轉(zhuǎn)效率作了一個(gè)簡單的測試與剖析。A冒泡排序：算法思想簡單描繪：在要排序的一組數(shù)中，對目前還未排好序的范圍內(nèi)的所有數(shù)，自上而下對相鄰的兩個(gè)數(shù)挨次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們交換。冒泡排序是穩(wěn)固的。算法時(shí)間復(fù)雜度：O(N2)下邊我們來測試試看不一樣數(shù)據(jù)量的排序時(shí)間：這是200個(gè)亂序隨機(jī)數(shù)：冒泡排序運(yùn)轉(zhuǎn)時(shí)間為毫秒這是1000個(gè)亂序隨機(jī)數(shù)：冒泡排序運(yùn)轉(zhuǎn)時(shí)間為毫秒這是5000個(gè)亂序隨機(jī)數(shù)：冒泡排序運(yùn)轉(zhuǎn)時(shí)間為毫秒這是20000個(gè)亂序隨機(jī)數(shù)：冒泡排序運(yùn)轉(zhuǎn)時(shí)間為毫秒從不一樣數(shù)據(jù)量的縱向剖析來看，1，在冒泡排序算法里，跟著數(shù)據(jù)量的增添，其運(yùn)轉(zhuǎn)時(shí)間也會(huì)愈來愈長。2，在兩百個(gè)數(shù)據(jù)的時(shí)候，其運(yùn)轉(zhuǎn)時(shí)間少到忽視不計(jì)，即運(yùn)算瞬時(shí)達(dá)成。這說明冒泡排序在辦理小數(shù)據(jù)量的時(shí)候仍是很給力的3，當(dāng)辦理的數(shù)據(jù)量從5000提到20000的時(shí)候，冒泡排序的運(yùn)轉(zhuǎn)時(shí)間發(fā)生了質(zhì)的增添。從幾十毫秒到幾千毫秒，運(yùn)轉(zhuǎn)時(shí)間大大增添，從這里可見，冒泡排序在辦理略微大的數(shù)據(jù)的時(shí)候便已經(jīng)展現(xiàn)出了力所不及感，我個(gè)人感覺已不大合用。簡單項(xiàng)選擇擇排序：算法思想簡單描繪：在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)地點(diǎn)的數(shù)交換；而后在剩下的數(shù)中間再找最小的與第二個(gè)地點(diǎn)的數(shù)交換，這樣循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。選擇排序是不穩(wěn)固的。時(shí)間復(fù)雜度：O(N2)下邊我們依舊來測試試看簡單項(xiàng)選擇擇排序在不一樣數(shù)據(jù)量的運(yùn)轉(zhuǎn)時(shí)間：這是200個(gè)亂序隨機(jī)數(shù)：簡單項(xiàng)選擇擇排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是1000個(gè)亂序隨機(jī)數(shù)：簡單項(xiàng)選擇擇排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是5000個(gè)亂序隨機(jī)數(shù)：簡單項(xiàng)選擇擇排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是20000個(gè)亂序隨機(jī)數(shù)：簡單項(xiàng)選擇擇排序運(yùn)轉(zhuǎn)時(shí)間：毫秒從不一樣數(shù)據(jù)量的縱向剖析來看，1，其運(yùn)轉(zhuǎn)時(shí)間跟著數(shù)據(jù)量的增添而增添2，簡單項(xiàng)選擇擇排序同冒泡排序相同，在辦理像200個(gè)這樣的小數(shù)據(jù)量的時(shí)候，其運(yùn)轉(zhuǎn)時(shí)間能夠忽視不計(jì)，即瞬時(shí)達(dá)成3，當(dāng)數(shù)據(jù)量從5000提升到20000的時(shí)候，其運(yùn)轉(zhuǎn)時(shí)間也是提升了幾十倍。直接插入排序算法思想簡單描繪：在要排序的一組數(shù)中，假定前面(n-1)[n>=2]個(gè)數(shù)已經(jīng)是排好次序的，此刻要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)也是排好次序的。這樣頻頻循環(huán)，直到所有排好次序。直接插入排序是穩(wěn)固的。算法時(shí)間復(fù)雜度：O(N2)下邊我們來簡單測試試看直接插入排序在不一樣數(shù)據(jù)量下的運(yùn)轉(zhuǎn)時(shí)間：這是200個(gè)亂序隨機(jī)數(shù)：直接插入排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是1000個(gè)亂序隨機(jī)數(shù)：直接插入排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是5000個(gè)亂序隨機(jī)數(shù)：直接插入排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是20000個(gè)亂序隨機(jī)數(shù)：直接插入排序運(yùn)轉(zhuǎn)時(shí)間：毫秒從不一樣數(shù)據(jù)量的縱向剖析來看：直接插入排序在想200個(gè)這樣的小數(shù)據(jù)量的時(shí)候履行特別快，效率高。當(dāng)數(shù)據(jù)量增添的20000的時(shí)候，運(yùn)轉(zhuǎn)時(shí)間會(huì)猛增幾十倍，效率體現(xiàn)降落趨向。D希爾排序算法思想簡單描繪：在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增添1個(gè)節(jié)點(diǎn)，而且對插入下一個(gè)數(shù)沒有供給任何幫助。假如比較相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)挪動(dòng)時(shí)能越過多個(gè)元素，則進(jìn)行一次比較便可能除去多個(gè)元故舊換。算法先將要排序的一組數(shù)按某個(gè)增量d分紅若干組，每組中記錄的下標(biāo)相差

d.對每組中所有元素進(jìn)行排序，而后再用一個(gè)較小的增量對它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到

1時(shí)，整個(gè)要排序的數(shù)被分紅一組，排序達(dá)成。希爾排序是不穩(wěn)固的。希爾排序時(shí)間復(fù)雜度：O（均勻）最好的O(N)最差的O(N2)下邊我們來簡單測試試看希爾排序在不一樣數(shù)據(jù)量的運(yùn)轉(zhuǎn)時(shí)間狀況：這是200個(gè)亂序隨機(jī)數(shù)：希爾排序運(yùn)轉(zhuǎn)時(shí)間為：毫秒這是1000個(gè)亂序隨機(jī)數(shù)：希爾排序的運(yùn)轉(zhuǎn)時(shí)間：毫秒這是5000個(gè)亂序隨機(jī)數(shù)：希爾排序的運(yùn)轉(zhuǎn)時(shí)間：毫秒這是20000個(gè)亂序隨機(jī)數(shù)：希爾排序的運(yùn)轉(zhuǎn)時(shí)間：毫秒從不一樣數(shù)據(jù)量的縱向剖析來看：從200個(gè)到20000量的隨機(jī)數(shù)，希爾排序運(yùn)轉(zhuǎn)的時(shí)間都是特別快的，效率極高。20000個(gè)數(shù)據(jù)的時(shí)候也不過不過5毫秒，這說明希爾排序在辦理大數(shù)據(jù)的能力上特別優(yōu)勝。E堆排序算法思想簡單描繪：堆排序是一種樹形選擇排序，是對直接選擇排序的有效改良。堆的定義以下：擁有n個(gè)元素的序列（h1,h2,...,hn),當(dāng)且僅當(dāng)知足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)時(shí)稱之為堆。在這里只議論知足前者條件的堆。由堆的定義能夠看出，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)。完整二叉樹能夠很直觀地表示堆的構(gòu)造。堆頂為根，其余為左子一個(gè)堆，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最大。而后將根節(jié)點(diǎn)與堆的最后一個(gè)節(jié)點(diǎn)交換。而后對前面(n-1)個(gè)數(shù)從頭調(diào)整使之成為堆。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對它們作交換，最后獲得有n個(gè)節(jié)點(diǎn)的有序序列。從算法描繪來看，堆排序需要兩個(gè)過程，一是成立堆，二是堆頂與堆的最后一個(gè)元故舊換地點(diǎn)。因此堆排序有兩個(gè)函數(shù)構(gòu)成。一是建堆的浸透函數(shù)，二是頻頻調(diào)用浸透函數(shù)實(shí)現(xiàn)排序的函數(shù)。堆排序是不穩(wěn)固的。算法時(shí)間復(fù)雜度：O(nlog2n)。下邊我們測試試看堆排序在不一樣數(shù)據(jù)量的運(yùn)轉(zhuǎn)成效：這是200個(gè)亂序隨機(jī)數(shù)：堆排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是1000個(gè)亂序隨機(jī)數(shù)：堆排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是5000個(gè)亂序隨機(jī)數(shù)：堆排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是20000個(gè)亂序隨機(jī)數(shù)：堆排序運(yùn)轉(zhuǎn)時(shí)間：毫秒從不一樣數(shù)據(jù)量的縱向剖析來看：堆排序不由在辦理小數(shù)據(jù)的時(shí)候效率特別高，就算辦理幾萬個(gè)數(shù)據(jù)，也幾乎是瞬時(shí)達(dá)成。從200到20000個(gè)數(shù)據(jù)的運(yùn)轉(zhuǎn)結(jié)果來看，堆排序在辦理大數(shù)據(jù)的能力上仍是很強(qiáng)的。迅速排序算法思想簡單描繪：迅速排序是對冒泡排序的一種實(shí)質(zhì)改良。它的基本思想是經(jīng)過一趟掃描后，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只好保證最大數(shù)值的數(shù)移到正確地點(diǎn)，而待排序序列的長度可能只減少1。迅速排序經(jīng)過一趟掃描，就能保證某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左側(cè)各數(shù)都比它小，右側(cè)各數(shù)都比它大。而后又用相同的方法辦理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。明顯迅速排序能夠用遞歸實(shí)現(xiàn)，自然也能夠用?；膺f歸實(shí)現(xiàn)。迅速排序是不穩(wěn)固的。最理想狀況算法時(shí)間復(fù)雜度：O(nlog2n)，最壞O(n2)下邊我們測試試看迅速排序在不一樣數(shù)據(jù)量的運(yùn)轉(zhuǎn)狀況：這是200個(gè)亂序隨機(jī)數(shù)：迅速排序運(yùn)轉(zhuǎn)時(shí)間毫秒這是1000個(gè)亂序隨機(jī)數(shù)：迅速排序運(yùn)轉(zhuǎn)時(shí)間：毫秒這是5000個(gè)亂序隨機(jī)數(shù)：迅速排序運(yùn)轉(zhuǎn)時(shí)間毫秒這是20000個(gè)亂序隨機(jī)數(shù)：迅速排序運(yùn)轉(zhuǎn)時(shí)間毫秒從不一樣數(shù)據(jù)量縱向剖析來看：跟著數(shù)據(jù)量的增添，迅速排序運(yùn)轉(zhuǎn)的時(shí)間也愈來愈長在辦理小數(shù)據(jù)量的時(shí)候，迅速排序效率特別高在辦理大數(shù)據(jù)的時(shí)候，運(yùn)轉(zhuǎn)時(shí)間所花的也不是很長，是能夠接受的，個(gè)人以為迅速排序是一種比較均衡的算法。橫向剖析這6種排序算法的效率：在辦理小數(shù)據(jù)量的時(shí)候，6中排序算法的效率都是特別可觀的，都是能夠接受的。但依據(jù)算法詳細(xì)來看