算法分析作業(yè)1_簡(jiǎn)單排序算法分析

1、排序算法復(fù)雜性分析一秦健劉鵬劉明歡我們鄭重承諾，本作業(yè)的內(nèi)容均為原創(chuàng)，沒有任何抄襲他人成果的行為，也不存在他人代寫作業(yè)和程序的行為。引用他人成果或公開資料的部分都已經(jīng)按照正確的格式在參考文獻(xiàn)中標(biāo)出。作者簽字得分統(tǒng)計(jì)學(xué)生填寫老師填寫姓名學(xué)號(hào)工作所占比例得分分別得分秦健2013140134%劉鵬2013140033%劉明歡2013071133%摘要本文通過三種簡(jiǎn)單排序-插入、冒泡和選擇排序算法并運(yùn)用C+語(yǔ)言編程實(shí)現(xiàn)，以計(jì)算簡(jiǎn)單排序算法復(fù)雜度。首先，利用不同規(guī)模下隨機(jī)產(chǎn)生的不同序列，計(jì)算三種排序方法下的元運(yùn)算-比較、交換、移動(dòng)的次數(shù)來定量刻畫排序算法的時(shí)間復(fù)雜度，即序列規(guī)模與元運(yùn)算次數(shù)的關(guān)系，得到三

2、種算法的時(shí)間復(fù)雜度均為n2，這說明這三種排序算法具有相同時(shí)間復(fù)雜度，并且實(shí)現(xiàn)簡(jiǎn)單，所以也歸為一類簡(jiǎn)單排序算法。其次，采用統(tǒng)一規(guī)模下的不同排列順序，主要是兩個(gè)極端序-順序、逆序的情況下分析三種算法的時(shí)間復(fù)雜度，得到算法的最好時(shí)間復(fù)雜度為1，最壞時(shí)間復(fù)雜度為n2，反映出不同順序的序列導(dǎo)致的排序算法時(shí)間復(fù)雜度的巨大差異性，并且插入、冒泡排序與選擇排序之間的優(yōu)劣也逐漸顯現(xiàn)出來，主要是由于逆序?qū)Φ臄?shù)目導(dǎo)致交換次數(shù)變化的緣故。最后，本文將作為其他排序算法的時(shí)間復(fù)雜度作為后續(xù)擴(kuò)展部分，以待完善。本文將圍繞以下兩個(gè)問題進(jìn)行討論分析:1） 設(shè)計(jì)一個(gè)程序，程序的輸入為n個(gè)（n必須要從鍵盤輸入）0到10000的正整

3、數(shù)（正整數(shù)可以是隨機(jī)產(chǎn)生），輸出為對(duì)這n個(gè)數(shù)進(jìn)行從小到大排序后的序列。排序方法分別使用插入排序、冒泡排序和選擇排序。2） 以兩個(gè)數(shù)比較、兩個(gè)數(shù)交換、移動(dòng)一個(gè)數(shù)為基本計(jì)算單位，測(cè)試你所編寫的程序?qū)τ趎=100,500,1000,2000四種輸入規(guī)模的時(shí)間復(fù)雜度。一、算法復(fù)雜度1.1算法復(fù)雜性算法的復(fù)雜性是算法效率的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上面，所需的資源越多，我們就說該算法的復(fù)雜性越高；反之，所需的資源越低，則該算法的復(fù)雜性越低。  計(jì)算機(jī)的資源，最重要的是時(shí)間和空間（即存儲(chǔ)器）資源。因而，算法的復(fù)雜性有時(shí)

4、間復(fù)雜性和空間復(fù)雜性之分。1.2時(shí)間復(fù)雜度【1】如果分別用N,I和A表示算法要解的問題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，把時(shí)間復(fù)雜性和空間復(fù)雜性分別用T和S來表示那么有 C=FN,I,A T=TN,I,A -(1)S=SN,I,A設(shè)計(jì)算機(jī)所提供的元運(yùn)算有k種，分別記為1,2,k。又設(shè)每執(zhí)行一次這些元運(yùn)算所需要的時(shí)間分別為t1,t2,tk。經(jīng)統(tǒng)計(jì)用到的元運(yùn)算i的次數(shù)為ei,i=1,2,k，則有ei=eiN,I。因此，TN,I=i=1ktieiN,I。記最壞情況、最好情況和平均情況下的時(shí)間復(fù)雜性，并分別有 TmaxN=maxIDNTN,I=maxIDNi=1ktieiN,I=TN,

5、I*TminN=minIDNTN,I=minIDNi=1ktieiN,I=TN,I TavgN=i=1kP(I)TN,I=i=1kP(I)i=1ktieiN,I其中，DN是規(guī)模為N的合法輸入的集合；I*, I分別是DN中使TN,I*達(dá)到TmaxN的合法輸入與使TN,I達(dá)到TminN的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。二、簡(jiǎn)單排序算法2.1簡(jiǎn)單排序法思想【2】2.1.1插入排序有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)

6、中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置），而第二部分就只包含這一個(gè)元素（即待插入元素）。在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中。2.1.2冒泡排序重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。冒泡排序是這樣實(shí)現(xiàn)的：首先從列表的第一個(gè)數(shù)字到倒數(shù)第二個(gè)數(shù)字，逐個(gè)檢查：若某一位上的數(shù)字大于他的下一位，則將它與它的下一位交

7、換。然后重復(fù)1號(hào)步驟，直至再也不能交換。2.1.3選擇排序選擇排序工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：初始狀態(tài)：無序區(qū)為R1.n，有序區(qū)為空。第1趟排序在無序區(qū)R1.n中選出關(guān)鍵字最小的記錄Rk，將它與無序區(qū)的第1個(gè)記錄R1交換，使R1.1和R2.n分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。2.2簡(jiǎn)單排序法流程圖此處僅給出選擇排序算法流程圖，冒泡、插入排序算法流程圖可根據(jù)2.1算法步驟類似給出。2.3簡(jiǎn)單排序法偽代碼同理,此

8、處僅給出插入排序算法偽代碼，冒泡、選擇排序算法偽代碼可根據(jù)附錄中的程序類似給出。INSERTION-SORT(A)Begin1 forj=0 to lengthA-12 if Aj>Aj+1 then key=Aj3 /InsertAj+1 into the sorted sequence A0.j.4 i=j+15 while i>0 and Ai <key6 Ai+1->key 7 Ai ->Ai+18 i=i-19 print AiEnd 三、算法實(shí)現(xiàn)與分析3.1時(shí)間復(fù)雜度-規(guī)模分析利用C+面對(duì)對(duì)象編程語(yǔ)言在VC+6.0編譯環(huán)境下進(jìn)行三種簡(jiǎn)單排序算法的編程實(shí)

9、現(xiàn)，關(guān)鍵代碼詳見附錄，程序結(jié)果截圖詳見附錄，整理結(jié)果如下表1所示:排序算法序列規(guī)模交換次數(shù)比較次數(shù)元運(yùn)算次數(shù)插入排序100245525495004500665846707713366110002513452523365036812000100917410111682020342冒泡排序1002455494974045006658412468419126810002513454884727508172000100917419987003007874選擇排序10093495050435004921247501252421000995499500500495200019871990002000987

10、表1簡(jiǎn)單排序算法時(shí)間復(fù)雜度從表1可以看出隨著排序序列規(guī)模的增加，插入排序和冒泡排序算法元運(yùn)算次數(shù)較選擇排序算法運(yùn)算次數(shù)增加愈加明顯，這主要是由于交換次數(shù)所造成的，本質(zhì)上是由于插入和排序的交換為相鄰交換，可能會(huì)增加逆序?qū)Φ臄?shù)目，導(dǎo)致下一次循環(huán)交換次數(shù)增多，而選擇排序的交換為最值交換，從表1也可以看出選擇排序算法的交換次數(shù)和序列規(guī)模基本一致，這是因?yàn)槊看窝h(huán)最值只有一個(gè)，交換一次就減少一個(gè)。并且從表1可以看出插入和冒泡排序的交換次數(shù)是一樣的，說明插入排序的移位操作本質(zhì)上就是相鄰交換，只不過交換順序?yàn)槊芭萁粨Q的逆過程。此外，冒泡排序的比較次數(shù)明顯高于插入排序和選擇排序這是因?yàn)槊芭菖判蛎看窝h(huán)僅僅減少

11、一次比較運(yùn)算，直到序列全部順序。但是上表卻不能明顯顯示出三種排序算法的時(shí)間復(fù)雜度和序列規(guī)模的關(guān)系，所以利用Excel數(shù)據(jù)作圖1: 圖1 簡(jiǎn)單排序算法復(fù)雜度折線從圖中可以看出三種簡(jiǎn)單的排序算法的時(shí)間復(fù)雜度的曲線增長(zhǎng)趨勢(shì)基本一致，基本處于線性和平方項(xiàng)之間，進(jìn)一步分析程序算法，從兩層循環(huán)遍歷可以得出三種簡(jiǎn)單排序算法的時(shí)間復(fù)雜度為n2，這與圖1顯示的結(jié)果基本吻合。3.2時(shí)間復(fù)雜度-排列分析由于初始序列的隨機(jī)性難免使得部分結(jié)果出現(xiàn)偏差，就統(tǒng)一規(guī)模而言，選擇兩種固定的初始排列-順序、逆序排列，考慮極端序下三種排序算法的時(shí)間復(fù)雜度，如下圖2、圖3所示:圖2 順序初始排序自然可以想到順序排序的序列不需要任何交

12、換，但是需要一次遍歷確定順序排序，所以比較次數(shù)即為一次循環(huán)的次數(shù)，相比之下，選擇排序卻需要每次遍歷重復(fù)確定每個(gè)最值，所以導(dǎo)致比較次數(shù)十分巨大，由此可知當(dāng)原始序列接近于順序或逆序?qū)?shù)較少時(shí)，采用插入和冒泡排序優(yōu)于選擇排序。由于沒有逆序?qū)Φ漠a(chǎn)生所以插入、冒泡排序算法的時(shí)間復(fù)雜度為1，即最好時(shí)間復(fù)雜度，而選擇排序的時(shí)間復(fù)雜度卻仍然為n2，這是由于龐大的比較次數(shù)所造成的。圖3逆序排序同理，另一個(gè)極端即逆序，此時(shí)逆序?qū)Φ臄?shù)目是最大的，插入和冒泡排序算法的交換次數(shù)和比較次數(shù)相接近，但是選擇排序優(yōu)于最值的數(shù)目不變，所以交換次數(shù)大大降低，而且逆序條件下最值分布的對(duì)稱性進(jìn)一步減少了選擇排序算法的交換次數(shù)。由此可

13、知當(dāng)原始序列接近于逆序或逆序?qū)?shù)較多時(shí)，采用插入和冒泡排序優(yōu)于選擇排序。此時(shí)，三種排序算法的時(shí)間復(fù)雜度均為n2，即最壞時(shí)間復(fù)雜度，而選擇排序的時(shí)間由于交換次數(shù)的較少，在常數(shù)項(xiàng)倍數(shù)下優(yōu)于其余兩種排序算法，但是比較次數(shù)的影響仍然使得算法并未得到量級(jí)上的優(yōu)化。四、延展推廣本文將作為其他排序算法-快速排序、希爾排序、堆排序、技術(shù)排序的時(shí)間復(fù)雜度作為后續(xù)擴(kuò)展部分，其他排序算法在交換次數(shù)和比較次數(shù)上的優(yōu)勢(shì)將明顯體現(xiàn)出來，通過數(shù)據(jù)結(jié)構(gòu)分析可以分析出其時(shí)間復(fù)雜度為nlogn，但是運(yùn)算優(yōu)化也將使得算法復(fù)雜的代價(jià)，使得編程較難編寫，難于維護(hù)。五、參考文獻(xiàn)1王曉東.算法設(shè)計(jì)與分析M.北京:清華大學(xué)出版社.2014(

14、2015.10重印)2 附錄簡(jiǎn)單排序結(jié)果截圖簡(jiǎn)單排序元計(jì)算截圖100規(guī)模500規(guī)模1000規(guī)模2000規(guī)模簡(jiǎn)單排序C+程序關(guān)鍵代碼void Sort:Insert_Sort()/插入排序算法cout<<"*"cout<<"insert sort data:"<<endl;Clear();/Display();int i,j;for (i=0;i<n-1;i+)if (newdatai>newdatai+1)j=i+1;while (j!=0)if (newdataj>=newdataj-1)compa

15、retimes+;break;swap(newdataj,newdataj-1);swaptimes+;comparetimes+;j-;/Display();elsecomparetimes+;Display(1);void Sort:Bubble_Sort()/冒泡排序算法cout<<"*"cout<<"bubble sort data:"<<endl;Clear();/Display();int i,j;int beforeswap=-1; for (i=n-1;i>0;i-) if (beforeswap

16、=swaptimes)break;elsebeforeswap=swaptimes;for (j=n-1;j>n-i-1;j-)if (newdataj-1>newdataj)swap(newdataj-1,newdataj);swaptimes+;comparetimes+;/Display();elsecomparetimes+; Display(1);void Sort:Comparison_Sort()/選擇排序算法cout<<"*"cout<<"comparison sort data:"<<endl;Clear();/Display();int i,j,k;int minnum;for (i=0;i<n;i+)k=i;minnum=newdatai;for (j=i+1;j<n;j+)if (newdataj<minnum)k=j;min