誰(shuí)有 算法設(shè)計(jì)與分析習(xí)題解答(第4版),求教材百度網(wǎng)盤(pán)??!急急急!
算法設(shè)計(jì)與分析習(xí)題解答(第4版)百度網(wǎng)盤(pán)在線觀看資源,免費(fèi)分享給您:
提取碼:1234
本書(shū)是《算法設(shè)計(jì)與分析(第4版)》配套輔助教材。本書(shū)將結(jié)合原教材的內(nèi)容,進(jìn)一步討論和講解原教材中的重點(diǎn)和難點(diǎn),問(wèn)題分析,求解思路和方法,為讀者深刻體會(huì)問(wèn)題求解的核心思想提供幫助。由于原教材的內(nèi)容有一定的深度和難度,讀者在學(xué)習(xí)和解答習(xí)題過(guò)程中會(huì)遇到一定的困難,因此本書(shū)選擇了原教材的一些典型的習(xí)題和難題,給出詳細(xì)的解答和分析。本書(shū)內(nèi)容豐富,觀點(diǎn)新穎,理論聯(lián)系實(shí)際。不僅可用作高等學(xué)校計(jì)算機(jī)專業(yè)本科生和研究生學(xué)習(xí)計(jì)算機(jī)算法設(shè)計(jì)的教材,而且也適合廣大工程技術(shù)人員和自學(xué)讀者學(xué)習(xí)參考。
畢業(yè)論文答辯的PPT應(yīng)該包含哪些內(nèi)容?
1、首先,PPT封面應(yīng)該有:畢設(shè)題目、答辯人、指導(dǎo)教師以及答辯日期;
2、其次,需要有一個(gè)目錄頁(yè)來(lái)清楚的闡述本次答辯的主要內(nèi)容有哪些;
3、接下來(lái),就到了答辯的主要內(nèi)容了,第一塊應(yīng)該介紹課題的研究背景與意義;
4、之后,是對(duì)于研究?jī)?nèi)容的理論基礎(chǔ)做一個(gè)介紹,這一部分簡(jiǎn)略清晰即可;
5、重頭戲自然是自己的研究?jī)?nèi)容,這一部分最好可以讓不太了解相關(guān)方面的老師們也能聽(tīng)出個(gè)大概,知道到底都做出了哪些工作,研究成果有哪些,研究成果究竟怎么樣;
6、最后,是對(duì)工作的一個(gè)總結(jié)和展望。
7、結(jié)束要感謝一下各位老師的指導(dǎo)與支持。
編寫(xiě)冒泡排序算法 冒泡排序算法的分析與改進(jìn) 算法設(shè)計(jì)
冒泡排序算法的分析與改進(jìn)
孫偉
(安徽中醫(yī)學(xué)院 醫(yī)藥信息工程學(xué)院 09醫(yī)軟一班,安徽合肥,230009)
摘 要: 冒泡排序算法有兩個(gè)優(yōu)點(diǎn):1“編程復(fù)雜度”很低,很容易寫(xiě)出代碼;2. 具有穩(wěn)定性,這里的穩(wěn)定性是指原序列中相同元素的相對(duì)順序仍然保持到排序后的序列,但當(dāng)需要排序的數(shù)據(jù)較多且無(wú)序時(shí),冒泡排序算法的時(shí)間復(fù)雜度較大,比較次數(shù)較多,本文提出了一種冒泡排序算法的改進(jìn)方法,可以大大減少比較的次數(shù),降低算法的時(shí)間復(fù)雜度。 關(guān)鍵詞:交換排序 掃描 穩(wěn)定 算法 中圖分類號(hào):TU 411.01 文獻(xiàn)標(biāo)識(shí)碼:A
Bubble sort algorithm analysis and improvement
SUN Wei
(Anhui University of Traditional Chinese Medicine Medical Information Engineering, Hefei 230009, China ;)
Abstract: Bubble sort algorithm has two advantages:1 “Programming complexity”is very low,and it is easy to write code;2.It has the stability, the stability refers to the original sequence in the same element relative sequence remains to sort sequence, but when the need to sort the data and more disordered, bubble sort algorithm time complexity compared to larger, more often, this paper presents a bubble sort algorithm method, can greatly reduce the number of comparisons, reduce the time complexity of algorithm.
Key words:Exchange sort ; Scanning ; stability ; Algorithm
1. 概述
1.1 冒泡排序簡(jiǎn)介
冒泡排序法是一種交換排序法,這種方法的基本思想是,將待排序
的元素看作是豎著排列的“ 氣泡”,較小的元素比較輕,從而要往上浮。在冒泡排序算法中我們要對(duì)這個(gè)“ 氣泡”序列處理若干遍。所謂一遍處理,就是自底向上檢查一遍這個(gè)序列,并時(shí)刻注意兩個(gè)相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個(gè)相鄰元素的順序不對(duì),即“ 輕”的元素在下面,就交換它們的位置。顯然,處理一遍之后,“ 最輕”的元素就浮到了最高位置;處理二遍之后,“ 次輕”的元素就浮到了次高位置。在作第二遍處理時(shí),由于
最高位置上的元素已是“ 最輕”元素,所以不必檢查。一般地,第i 遍處理時(shí),不必檢查第i 高位置以上的元素,因?yàn)榻?jīng)過(guò)前面i- 1遍的處理,它們已正確地排好序。
1.2 冒泡排序方法
冒泡排序法是一種最簡(jiǎn)單的排序算法, 它和氣泡從水中往上冒的情況有些類似。其基本算法如下:對(duì)1 至n 個(gè)記錄,先將第n 個(gè)和第n- 1 個(gè)記錄的鍵值進(jìn)行比較,如r [n].key
——————————————————————————————————————————————————————— 收稿日期:2012-4-14;
作者簡(jiǎn)介:孫偉 1992-10-04 女 09713033 09醫(yī)軟一班
實(shí)現(xiàn)的功能:將鍵值最小的記錄傳到了第1 位。然后,再對(duì)2 至n 個(gè)記錄進(jìn)行同樣操作,則具有次小鍵值的記錄被安置在第2 位上。重復(fù)以上過(guò)程, 每次的移動(dòng)都向最終排序的目標(biāo)前進(jìn),直至沒(méi)有記錄需要交換為止。具體實(shí)現(xiàn)時(shí),可以用一支旗子flag 表示第i 趟是否出現(xiàn)交換。如果第i 趟沒(méi)有交換,則表示此時(shí)已完成排序,因而可以終止。
1.3 冒泡排序過(guò)程示例
設(shè)待排序的鍵值為: 25 17 65 13 94 47 41 94
執(zhí)行冒泡排序的過(guò)程如下圖所示。其中,第一列為初始鍵值序列, 第二列至第八列依次為各趟排序的結(jié)果, 圖中用方括號(hào)括起來(lái)的是當(dāng)前待排序的無(wú)序區(qū)。
每一次排序都使有序區(qū)擴(kuò)充了一個(gè)氣泡,在經(jīng)過(guò)i 次排序之后,有序區(qū)中就有i 個(gè)氣泡, 而無(wú)序區(qū)中氣泡的重量總是大于等于有序區(qū)中氣泡的重量,整個(gè)冒泡排序過(guò)程至多需要進(jìn)行n- 1 次排序。但是, 若在某一次排序中未發(fā)現(xiàn)氣泡位置的交換, 則說(shuō)明待排序的無(wú)序區(qū)中所有氣泡均滿足輕者在上,重者在下的原則因此冒泡排序過(guò)程可在此次排序后終止。在上圖的示例中,在第四次(圖中第五列) 排序過(guò)程中就沒(méi)有氣泡交換位置, 此時(shí)整個(gè)文件已達(dá)到有序狀態(tài)。為此,實(shí)際給出的算法中, 我們可以引入一個(gè)布爾量flag , 在每一次排序之前, 先將它置為true ,若在一次排序中交換了記錄, 則將它置為false 。當(dāng)一次排序結(jié)束時(shí),我們?cè)贆z查flag ,若未曾交換過(guò)記錄便終止算法。
該算法的時(shí)間復(fù)雜性為0(n2), 算法為穩(wěn)定的排序方法。
2. 對(duì)于冒泡算法的改進(jìn)
2.1 第一種改進(jìn)方法
如果在某一趟循環(huán)中沒(méi)有任何數(shù)據(jù)交換發(fā)生, 則表明數(shù)據(jù)已經(jīng)排序完畢。那么剩余的循環(huán)就不需要再執(zhí)行假設(shè)需要排序的數(shù)據(jù)已經(jīng)按照從小到大排列,那么第一趟比較就不會(huì)有任何數(shù)據(jù)交換發(fā)生。這種改進(jìn)算法如下:
設(shè)置一個(gè)標(biāo)志位,當(dāng)沒(méi)有交換的時(shí)候這個(gè)標(biāo)志位不會(huì)變化,那么說(shuō)明數(shù)據(jù)已經(jīng)排序好了,就不需要再進(jìn)行剩余的循環(huán)。只有在標(biāo)志位被重新設(shè)置的情況下才會(huì)進(jìn)行剩余的循環(huán)。
public static
void ImproveBubble1(int [ ]myArray) {
bool isSorted = false;
for(int i = 0; i
// 只有在沒(méi)有排序的情況下才繼續(xù)循環(huán) { isSorted =
true; // 設(shè)定排序標(biāo)志
for(int j = 0; j
myArray[j+1] ) { isSorted =
false; // 如果是沒(méi)有排序,就重新設(shè)定標(biāo)志 Swap(refmyArray, refmyArray[i+1]);
} } } }
從這種算法可以看出,若記錄的初始狀態(tài)是正序( 從小到大) 的,則一趟掃描即可完成排序。所需的較和記錄移動(dòng)的次數(shù)分別達(dá)到最小值n- 1 和0。即算法最好的時(shí)間復(fù)雜度為0(n);若初始記錄是反序( 從大到?。?的,則需要進(jìn)行n- 1 趟排序,每趟排序要進(jìn)行n- i 次關(guān)鍵字的比較,且每次比較都必須移記錄三次來(lái)達(dá)到交換記錄位置。在這情況下比較和移動(dòng)次數(shù)達(dá)到最大值:比較次數(shù):Cmax= n(n- 1)/2 移動(dòng)次數(shù): Mmax=3n(n- 1)/2因此這種改進(jìn)方法的最壞時(shí)間復(fù)雜度也為0(n^2)。在平均情況下,算法可能在中間的某一趟排序完后就終止,但總的比較次數(shù)仍為0(n^2),所以算法的
平均時(shí)間復(fù)雜度為0(n^2)。因此,這種算法最好的時(shí)間復(fù)雜度為0(n)。平均,最壞時(shí)刻復(fù)雜度為0(n^2)。
2.2 第二種改進(jìn)方法
在冒泡排序的每趟掃描中, 記住最后一次交換發(fā)生的位置lastexchange 也能有所幫助。因?yàn)樵撐恢弥暗南噜徲涗浺呀?jīng)有序,故下一趟排序開(kāi)始的時(shí)候,0 到lastexchange 已經(jīng)是有序的了,lastexchange 到n- 1是無(wú)序區(qū)。所以一趟排序可能使當(dāng)前有序區(qū)擴(kuò)充多個(gè)記錄。即較大縮小無(wú)序區(qū)范圍,而非遞減1,以此減少排序趟數(shù)。這種算法如下:
在冒泡排序中,每趟排序?qū)崿F(xiàn)了將最大(升序) 或最小(降序) 的記錄安置到未排序部分的最后位置,即最終位置。通過(guò)進(jìn)一步觀察研究,由于每趟排序過(guò)程中,通過(guò)和鄰記錄關(guān)鍵字兩兩比較,大(升序) 或小(降序) 的記錄在不斷地往下沉或往后靠,小(升序) 或大(降序) 的記錄在不斷往上冒或往前靠。每經(jīng)過(guò)一趟排序,在最后次交換位置后面的記錄都已經(jīng)排好序。根據(jù)上面的思路,對(duì)n 個(gè)記錄進(jìn)行第k 趟排序,首先需在第k- 1 趟排序時(shí)記下最后交換的位置。然后在第k 趟排序時(shí),將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較,符合交換條件時(shí),進(jìn)行交換。再比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字,依次類推,直至第m- 1 個(gè)記錄和第m 個(gè)記錄的關(guān)鍵字進(jìn)行比較,而不需要比較至n- k- 1 個(gè)記錄。在大部分排序中,m 都小于n- k- 1從而減少了比較趟數(shù)和每趟的比較次數(shù)。由于在第一趟排序
時(shí),沒(méi)有上一趟排序的m 值。因此,還要設(shè)置m 的初始值為n- 1。
public static
void ImproveBubble2(int[ ]myArray) { int m= myArray.Length -1; int k, j; while(m> 0 )
{ for( k=j=0; j myArray[j+1]) {
Swap(refmyArray[j], refmyArray[j+1]);
k = j; // 記錄每次交換的位置 }}
m= k; // 記錄最后一個(gè)交換的位置 }}
從這種算法可以看出,若記錄的初始狀態(tài)是正序( 從小到大) 的。則一趟掃描即可完成排序, 所的關(guān)鍵比較和記錄移動(dòng)的次數(shù)分別達(dá)到最小值n- 1 和0。即算法最好的時(shí)間復(fù)雜度為0(n);若初始記錄是反序( 從大到小) 的,則需要進(jìn)行n- 1 趟排序,每趟排序要進(jìn)行n- i 次關(guān)鍵字的比較,且每次比較都須移動(dòng)記錄三次來(lái)達(dá)到交換記錄位置。在這情況下比較和移動(dòng)次數(shù)達(dá)到最大值:比較次數(shù):Cmax= n(n- 1)/2 移動(dòng)次數(shù)Mmax=3n(n- 1)/2因此,這種辦法的最壞時(shí)間復(fù)雜度也為0(n^2)。在平均情況下,算法較大地改變了無(wú)序區(qū)的范圍,從而減少了比較的次數(shù),但總的比較次數(shù)仍為0(n^2)。所以算法的平均時(shí)間復(fù)雜度為0(n^2)。因此,算法2 最好的時(shí)間復(fù)雜度為0(n)。平均,最壞時(shí)刻復(fù)雜度為0(n^2)。 2.3 雙向掃描冒泡法
若記錄的初始狀態(tài)為:只有最輕的氣泡位于d[n]的位置(或者最重的氣泡位于d[0]位置) ,其余的氣泡均已排好序。在上述三種算法中都要做n- 1 趟掃描。實(shí)際上只需一趟掃描就可以完成排序。所以對(duì)于這種不
對(duì)稱的情況??蓪?duì)冒泡排序又作一次改進(jìn)。在排序過(guò)程中交替改變掃描方向。即先從下掃到上,再?gòu)纳蠏叩较?,?lái)回地進(jìn)行掃描,這樣就得到雙向冒泡排序算法。
對(duì)n 個(gè)記錄進(jìn)行排序時(shí),設(shè)up 記錄了從前面向后面依次進(jìn)行掃描時(shí)最后的交換位置,low 記錄了從后面向前面依次進(jìn)行掃描時(shí)最前的交換位置。由上個(gè)改進(jìn)的冒泡排序的原理可知,up 后面的記錄和low 前面的記錄都已有序。每趟排序都由兩次不同方向的比較、交換組成。第一次是從未排好序的第一個(gè)記錄開(kāi)始,即從low 記錄開(kāi)始,向后依次兩兩比較,如果不符合條件,則交換之,
直至比較到未排好序的最后一個(gè)記錄,即up 記錄為止。同時(shí)記下最后一次交換的位置,并存于up 。第二次是從未排好序的最后一個(gè)記錄開(kāi)始, 即從up 記錄開(kāi)始,向前依次兩兩比較,如果不符合條件,則交換之,直至比較到未排好序的第一個(gè)記
錄,即low 記錄為止。同時(shí)記下最后次交換的位置,并存于low 。這樣,就完成了一趟排序。每趟排序都實(shí)現(xiàn)了將未排好序部分的關(guān)鍵字大的記錄往后移
(升序) ,
關(guān)鍵字小的記錄往前移( 升序) ,從而使
兩端已排好序( 如果是降序,記錄移動(dòng)的方向則相反) 。未排好序部分的記錄的首尾位置分別由low 和up 指明。不斷按上面的方法進(jìn)行排序,使兩端已排好序的記錄不斷增多,未排好序部分的記錄逐漸減少。即low 和up 的值不斷接近,當(dāng)low>=up 時(shí),表明已沒(méi)有未排好序的記錄,排序就完成了。由于在第一趟排序時(shí),沒(méi)有上趟排序的low 和up 值。因此,還要設(shè)置low 和up 的初始值分別為0 和n- 1。
public static
void ImproveBubble3(int [ ]myArray) { int low, up, index, i; low= 0;
up = myArray.Length - 1; index = low; while( up > low)
{ for( i=low; imyArray[i+1]) {
Swap(refmyArray, refmyArray[i+1]); index = i; }}
up= index; // 記錄最后一個(gè)交換的位置
for(i=up; i>low; i- - ) // 從最后一個(gè)交換
位置處從下向上掃描
{ if(myArray
Swap(refmyArray, refmyArray[i- 1]); index = i;
}} low= index; // 記錄最后一個(gè)交換的位
置
}}
從這種算法可以看出,若記錄的初始狀態(tài)是正
序( 從小到大) 的,則一趟掃描即可完成排序。所需的關(guān)鍵比較和記錄移動(dòng)的次數(shù)分別達(dá)到最小值n- 1 和0。即算法最好的時(shí)間復(fù)雜度為0(n);若初始記錄是反序( 從大到?。?的,則需要進(jìn)行[n/2]趟排序。如果只有最重的氣泡在最上面( 或者最輕的氣泡在最下面) ,其余的有序,這時(shí)候就只需要比較1 趟。但是在最壞的情況下,算法的復(fù)雜度也為0(n^2)。因此,算法最好的時(shí)間復(fù)雜度為0(n),最壞時(shí)刻復(fù)雜度為0(n^2)。
3. 性能分析
為了分析數(shù)據(jù)兩種冒泡排序法的性能, 我們用自編的測(cè)試程序?qū)Υ罅繑?shù)據(jù)進(jìn)行了測(cè)試,得出下表,從表中可以直觀地看出兩種冒泡排序方法的性能差異( 時(shí)間單位為毫秒)。
圖1 算法運(yùn)行時(shí)間比較表
4. 結(jié)束語(yǔ)
從上面的表格可以看出,在數(shù)據(jù)量比較小的時(shí)候,這幾種算法基本沒(méi)有任何區(qū)別。當(dāng)數(shù)據(jù)量比較大的時(shí)候,雙向掃描冒泡排序會(huì)有更好的效率。但是效率并沒(méi)有根本的提升。因此冒泡排序確實(shí)不是我們排序的首選。在數(shù)據(jù)量比較大的時(shí)候,快速排序等會(huì)有非常明顯的優(yōu)勢(shì)。但是在數(shù)據(jù)量很小的時(shí)候,各種排序算法的效率差別并不是很大。那么冒泡排序也會(huì)有自己的用武之地。因此,在實(shí)際考慮算法的時(shí)候,最重要的是熟悉各種算法的性能表現(xiàn)并且根據(jù)數(shù)據(jù)的數(shù)量以及當(dāng)前運(yùn)行的環(huán)境,開(kāi)發(fā)的進(jìn)度選擇最合適的算法。
[參 考 文 獻(xiàn)]
[1]( 美) 萊維丁著. 潘彥譯,《算法設(shè)計(jì)與分析基礎(chǔ)》. 清華大學(xué)出版社 [2] 胡金初,《計(jì)算機(jī)算法》. 清華大學(xué)出版社
[3] 阿蘇外耶(M.H.Alsuwaiyel),朱洪(譯),《算法設(shè)計(jì)技巧與分析》.電子工業(yè)出版社 [4](美)Robert sedgewick,《算法分析導(dǎo)論》.機(jī)械工業(yè)出版社
[5]( 美)Michael T.Goodrich Roberto Tamassia,《算法分析與設(shè)計(jì)》人民郵電出版社 [6]王曉東,《計(jì)算機(jī)算法設(shè)計(jì)與分析》電子工業(yè)出版社
[7]Shaffer,Clifford,張銘,《數(shù)據(jù)結(jié)構(gòu)與算法分析》電子工業(yè)出版社 [8]劉任任 ,《算法設(shè)計(jì)與分析》武漢理工大學(xué)出版社,2003