誰有 算法設計與分析習題解答（第4版），求教材百度網(wǎng)盤??！急急急！

算法設計與分析習題解答（第4版）百度網(wǎng)盤在線觀看資源，免費分享給您：

提取碼：1234

本書是《算法設計與分析（第4版）》配套輔助教材。本書將結合原教材的內(nèi)容，進一步討論和講解原教材中的重點和難點，問題分析，求解思路和方法，為讀者深刻體會問題求解的核心思想提供幫助。由于原教材的內(nèi)容有一定的深度和難度，讀者在學習和解答習題過程中會遇到一定的困難，因此本書選擇了原教材的一些典型的習題和難題，給出詳細的解答和分析。本書內(nèi)容豐富，觀點新穎，理論聯(lián)系實際。不僅可用作高等學校計算機專業(yè)本科生和研究生學習計算機算法設計的教材，而且也適合廣大工程技術人員和自學讀者學習參考。

畢業(yè)論文答辯的PPT應該包含哪些內(nèi)容？

1、首先，PPT封面應該有：畢設題目、答辯人、指導教師以及答辯日期；
2、其次，需要有一個目錄頁來清楚的闡述本次答辯的主要內(nèi)容有哪些；
3、接下來，就到了答辯的主要內(nèi)容了，第一塊應該介紹課題的研究背景與意義；
4、之后，是對于研究內(nèi)容的理論基礎做一個介紹，這一部分簡略清晰即可；
5、重頭戲自然是自己的研究內(nèi)容，這一部分最好可以讓不太了解相關方面的老師們也能聽出個大概，知道到底都做出了哪些工作，研究成果有哪些，研究成果究竟怎么樣；
6、最后，是對工作的一個總結和展望。
7、結束要感謝一下各位老師的指導與支持。

編寫冒泡排序算法 冒泡排序算法的分析與改進 算法設計

冒泡排序算法的分析與改進

孫偉

（安徽中醫(yī)學院 醫(yī)藥信息工程學院 09醫(yī)軟一班，安徽合肥，230009）

摘 要： 冒泡排序算法有兩個優(yōu)點：1“編程復雜度”很低，很容易寫出代碼；2. 具有穩(wěn)定性，這里的穩(wěn)定性是指原序列中相同元素的相對順序仍然保持到排序后的序列，但當需要排序的數(shù)據(jù)較多且無序時，冒泡排序算法的時間復雜度較大，比較次數(shù)較多，本文提出了一種冒泡排序算法的改進方法，可以大大減少比較的次數(shù)，降低算法的時間復雜度。 關鍵詞：交換排序 掃描 穩(wěn)定 算法 中圖分類號：TU 411.01 文獻標識碼：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 冒泡排序簡介

冒泡排序法是一種交換排序法，這種方法的基本思想是，將待排序

的元素看作是豎著排列的“ 氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個“ 氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，并時刻注意兩個相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個相鄰元素的順序不對，即“ 輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“ 最輕”的元素就浮到了最高位置；處理二遍之后，“ 次輕”的元素就浮到了次高位置。在作第二遍處理時，由于

最高位置上的元素已是“ 最輕”元素，所以不必檢查。一般地，第i 遍處理時，不必檢查第i 高位置以上的元素，因為經(jīng)過前面i- 1遍的處理，它們已正確地排好序。

1.2 冒泡排序方法

冒泡排序法是一種最簡單的排序算法, 它和氣泡從水中往上冒的情況有些類似。其基本算法如下：對1 至n 個記錄，先將第n 個和第n- 1 個記錄的鍵值進行比較，如r [n].key

——————————————————————————————————————————————————————— 收稿日期：2012-4-14；

作者簡介：孫偉 1992-10-04 女 09713033 09醫(yī)軟一班

實現(xiàn)的功能：將鍵值最小的記錄傳到了第1 位。然后，再對2 至n 個記錄進行同樣操作，則具有次小鍵值的記錄被安置在第2 位上。重復以上過程， 每次的移動都向最終排序的目標前進，直至沒有記錄需要交換為止。具體實現(xiàn)時，可以用一支旗子flag 表示第i 趟是否出現(xiàn)交換。如果第i 趟沒有交換，則表示此時已完成排序，因而可以終止。

1.3 冒泡排序過程示例

設待排序的鍵值為： 25 17 65 13 94 47 41 94

執(zhí)行冒泡排序的過程如下圖所示。其中，第一列為初始鍵值序列, 第二列至第八列依次為各趟排序的結果， 圖中用方括號括起來的是當前待排序的無序區(qū)。

每一次排序都使有序區(qū)擴充了一個氣泡，在經(jīng)過i 次排序之后，有序區(qū)中就有i 個氣泡， 而無序區(qū)中氣泡的重量總是大于等于有序區(qū)中氣泡的重量，整個冒泡排序過程至多需要進行n- 1 次排序。但是, 若在某一次排序中未發(fā)現(xiàn)氣泡位置的交換， 則說明待排序的無序區(qū)中所有氣泡均滿足輕者在上，重者在下的原則因此冒泡排序過程可在此次排序后終止。在上圖的示例中，在第四次(圖中第五列) 排序過程中就沒有氣泡交換位置, 此時整個文件已達到有序狀態(tài)。為此，實際給出的算法中， 我們可以引入一個布爾量flag ， 在每一次排序之前， 先將它置為true ，若在一次排序中交換了記錄, 則將它置為false 。當一次排序結束時，我們再檢查flag ，若未曾交換過記錄便終止算法。

該算法的時間復雜性為0(n2), 算法為穩(wěn)定的排序方法。

2. 對于冒泡算法的改進

2.1 第一種改進方法

如果在某一趟循環(huán)中沒有任何數(shù)據(jù)交換發(fā)生， 則表明數(shù)據(jù)已經(jīng)排序完畢。那么剩余的循環(huán)就不需要再執(zhí)行假設需要排序的數(shù)據(jù)已經(jīng)按照從小到大排列，那么第一趟比較就不會有任何數(shù)據(jù)交換發(fā)生。這種改進算法如下：

設置一個標志位，當沒有交換的時候這個標志位不會變化，那么說明數(shù)據(jù)已經(jīng)排序好了，就不需要再進行剩余的循環(huán)。只有在標志位被重新設置的情況下才會進行剩余的循環(huán)。

public static

void ImproveBubble1(int [ ]myArray) {

bool isSorted = false;

for(int i = 0; i

// 只有在沒有排序的情況下才繼續(xù)循環(huán) { isSorted =

true; // 設定排序標志

for(int j = 0; j

myArray[j+1] ) { isSorted =

false; // 如果是沒有排序，就重新設定標志 Swap(refmyArray, refmyArray[i+1]);

} } } }

從這種算法可以看出，若記錄的初始狀態(tài)是正序（ 從小到大） 的，則一趟掃描即可完成排序。所需的較和記錄移動的次數(shù)分別達到最小值n- 1 和0。即算法最好的時間復雜度為0(n)；若初始記錄是反序（ 從大到?。?的，則需要進行n- 1 趟排序，每趟排序要進行n- i 次關鍵字的比較，且每次比較都必須移記錄三次來達到交換記錄位置。在這情況下比較和移動次數(shù)達到最大值：比較次數(shù)：Cmax= n(n- 1)/2 移動次數(shù)： Mmax=3n(n- 1)/2因此這種改進方法的最壞時間復雜度也為0(n^2)。在平均情況下，算法可能在中間的某一趟排序完后就終止，但總的比較次數(shù)仍為0(n^2)，所以算法的

平均時間復雜度為0(n^2)。因此，這種算法最好的時間復雜度為0(n)。平均，最壞時刻復雜度為0(n^2)。

2.2 第二種改進方法

在冒泡排序的每趟掃描中， 記住最后一次交換發(fā)生的位置lastexchange 也能有所幫助。因為該位置之前的相鄰記錄已經(jīng)有序，故下一趟排序開始的時候，0 到lastexchange 已經(jīng)是有序的了，lastexchange 到n- 1是無序區(qū)。所以一趟排序可能使當前有序區(qū)擴充多個記錄。即較大縮小無序區(qū)范圍，而非遞減1，以此減少排序趟數(shù)。這種算法如下：

在冒泡排序中，每趟排序實現(xiàn)了將最大(升序) 或最小(降序) 的記錄安置到未排序部分的最后位置，即最終位置。通過進一步觀察研究，由于每趟排序過程中，通過和鄰記錄關鍵字兩兩比較，大(升序) 或小(降序) 的記錄在不斷地往下沉或往后靠，小(升序) 或大(降序) 的記錄在不斷往上冒或往前靠。每經(jīng)過一趟排序，在最后次交換位置后面的記錄都已經(jīng)排好序。根據(jù)上面的思路，對n 個記錄進行第k 趟排序，首先需在第k- 1 趟排序時記下最后交換的位置。然后在第k 趟排序時，將第一個記錄的關鍵字與第二個記錄的關鍵字進行比較，符合交換條件時，進行交換。再比較第二個記錄和第三個記錄的關鍵字，依次類推，直至第m- 1 個記錄和第m 個記錄的關鍵字進行比較，而不需要比較至n- k- 1 個記錄。在大部分排序中，m 都小于n- k- 1從而減少了比較趟數(shù)和每趟的比較次數(shù)。由于在第一趟排序

時，沒有上一趟排序的m 值。因此，還要設置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; // 記錄最后一個交換的位置 }}

從這種算法可以看出，若記錄的初始狀態(tài)是正序（ 從小到大） 的。則一趟掃描即可完成排序， 所的關鍵比較和記錄移動的次數(shù)分別達到最小值n- 1 和0。即算法最好的時間復雜度為0(n);若初始記錄是反序（ 從大到?。?的，則需要進行n- 1 趟排序，每趟排序要進行n- i 次關鍵字的比較，且每次比較都須移動記錄三次來達到交換記錄位置。在這情況下比較和移動次數(shù)達到最大值：比較次數(shù)：Cmax= n(n- 1)/2 移動次數(shù)Mmax=3n(n- 1)/2因此，這種辦法的最壞時間復雜度也為0(n^2)。在平均情況下，算法較大地改變了無序區(qū)的范圍，從而減少了比較的次數(shù)，但總的比較次數(shù)仍為0(n^2)。所以算法的平均時間復雜度為0(n^2)。因此，算法2 最好的時間復雜度為0(n)。平均，最壞時刻復雜度為0(n^2)。 2.3 雙向掃描冒泡法

若記錄的初始狀態(tài)為:只有最輕的氣泡位于d[n]的位置(或者最重的氣泡位于d[0]位置) ，其余的氣泡均已排好序。在上述三種算法中都要做n- 1 趟掃描。實際上只需一趟掃描就可以完成排序。所以對于這種不

對稱的情況。可對冒泡排序又作一次改進。在排序過程中交替改變掃描方向。即先從下掃到上，再從上掃到下，來回地進行掃描，這樣就得到雙向冒泡排序算法。

對n 個記錄進行排序時，設up 記錄了從前面向后面依次進行掃描時最后的交換位置，low 記錄了從后面向前面依次進行掃描時最前的交換位置。由上個改進的冒泡排序的原理可知，up 后面的記錄和low 前面的記錄都已有序。每趟排序都由兩次不同方向的比較、交換組成。第一次是從未排好序的第一個記錄開始，即從low 記錄開始，向后依次兩兩比較，如果不符合條件，則交換之，

直至比較到未排好序的最后一個記錄，即up 記錄為止。同時記下最后一次交換的位置，并存于up 。第二次是從未排好序的最后一個記錄開始, 即從up 記錄開始，向前依次兩兩比較，如果不符合條件，則交換之，直至比較到未排好序的第一個記

錄，即low 記錄為止。同時記下最后次交換的位置，并存于low 。這樣，就完成了一趟排序。每趟排序都實現(xiàn)了將未排好序部分的關鍵字大的記錄往后移

(升序) ，

關鍵字小的記錄往前移（ 升序) ，從而使

兩端已排好序（ 如果是降序，記錄移動的方向則相反) 。未排好序部分的記錄的首尾位置分別由low 和up 指明。不斷按上面的方法進行排序，使兩端已排好序的記錄不斷增多，未排好序部分的記錄逐漸減少。即low 和up 的值不斷接近，當low>=up 時，表明已沒有未排好序的記錄，排序就完成了。由于在第一趟排序時，沒有上趟排序的low 和up 值。因此，還要設置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; // 記錄最后一個交換的位置

for(i=up; i>low; i- - ) // 從最后一個交換

位置處從下向上掃描

{ if(myArray

Swap(refmyArray, refmyArray[i- 1]); index = i;

}} low= index; // 記錄最后一個交換的位

置

}}

從這種算法可以看出，若記錄的初始狀態(tài)是正

序（ 從小到大） 的，則一趟掃描即可完成排序。所需的關鍵比較和記錄移動的次數(shù)分別達到最小值n- 1 和0。即算法最好的時間復雜度為0(n);若初始記錄是反序（ 從大到?。?的，則需要進行[n/2]趟排序。如果只有最重的氣泡在最上面（ 或者最輕的氣泡在最下面） ，其余的有序，這時候就只需要比較1 趟。但是在最壞的情況下，算法的復雜度也為0(n^2)。因此，算法最好的時間復雜度為0(n)，最壞時刻復雜度為0(n^2)。

3. 性能分析

為了分析數(shù)據(jù)兩種冒泡排序法的性能， 我們用自編的測試程序對大量數(shù)據(jù)進行了測試，得出下表，從表中可以直觀地看出兩種冒泡排序方法的性能差異（ 時間單位為毫秒）。

圖1 算法運行時間比較表

4. 結束語

從上面的表格可以看出，在數(shù)據(jù)量比較小的時候，這幾種算法基本沒有任何區(qū)別。當數(shù)據(jù)量比較大的時候，雙向掃描冒泡排序會有更好的效率。但是效率并沒有根本的提升。因此冒泡排序確實不是我們排序的首選。在數(shù)據(jù)量比較大的時候，快速排序等會有非常明顯的優(yōu)勢。但是在數(shù)據(jù)量很小的時候，各種排序算法的效率差別并不是很大。那么冒泡排序也會有自己的用武之地。因此，在實際考慮算法的時候，最重要的是熟悉各種算法的性能表現(xiàn)并且根據(jù)數(shù)據(jù)的數(shù)量以及當前運行的環(huán)境，開發(fā)的進度選擇最合適的算法。

[參 考 文 獻]

［1］（ 美） 萊維丁著. 潘彥譯，《算法設計與分析基礎》. 清華大學出版社 ［2］ 胡金初，《計算機算法》. 清華大學出版社

［3］ 阿蘇外耶（M．H．Alsuwaiyel），朱洪（譯），《算法設計技巧與分析》．電子工業(yè)出版社 ［4］（美）Robert sedgewick，《算法分析導論》．機械工業(yè)出版社

［5］（ 美）Michael T．Goodrich Roberto Tamassia，《算法分析與設計》人民郵電出版社 ［6］王曉東，《計算機算法設計與分析》電子工業(yè)出版社

［7］Shaffer，Clifford，張銘，《數(shù)據(jù)結構與算法分析》電子工業(yè)出版社 ［8］劉任任 ，《算法設計與分析》武漢理工大學出版社，2003