演算法研究與設計

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

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

孫偉

（安徽中醫學院 醫葯信息工程學院 09醫軟一班，安徽合肥，230009）

摘 要： 冒泡排序演算法有兩個優點：1「編程復雜度」很低，很容易寫出代碼；2. 具有穩定性，這里的穩定性是指原序列中相同元素的相對順序仍然保持到排序後的序列，但當需要排序的數據較多且無序時，冒泡排序演算法的時間復雜度較大，比較次數較多，本文提出了一種冒泡排序演算法的改進方法，可以大大減少比較的次數，降低演算法的時間復雜度。 關鍵讓握坦詞：交坦桐換排序 掃描 穩定 演算法 中圖分類號：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 rece the number of comparisons, rece the time complexity of algorithm.

Key words：Exchange sort ; Scanning ; stability ; Algorithm

1. 概述

1.1 冒泡排序簡介

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

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

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

1.2 冒泡排序方法

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

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

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

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

1.3 冒泡排序過程示例

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

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

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

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

2. 對於冒泡演算法的改進

2.1 第一種改進方法

如果在某一趟循環中沒有任何數據交換發生， 則表明數據已經排序完畢。那麼剩餘的循環就不需要再執行假設需要排序的數據已經按照從小到大排列，那麼第一趟比較就不會有任何數據交換發生。這種改進演算法如下：

設置一個標志位，當沒有交換的時候這個標志位不會變化，那麼說明數據已經排序好了，就不需要再進行剩餘的循環。只有在標志位被重新設置的情況下才會進行剩餘的循環。

public static

void ImproveBubble1(int [ ]myArray) {

bool isSorted = false;

for(int i = 0; i

// 只有在沒有排序的情況下才繼續循環 { isSorted =

true; // 設定排序標志

for(int j = 0; j

myArray[j+1] ) { isSorted =

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

} } } }

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

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

2.2 第二種改進方法

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

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

時，沒有上一趟排序的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; // 記錄最後一個交換的位置 }}

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

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

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

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

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

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

(升序) ，

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

兩端已排好序（ 如果是降序，記錄移動的方向則相反) 。未排好序部分的記錄的首尾位置分別由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; // 記錄最後一個交換的位

置

}}

從這種演算法可以看出，若記錄的初始狀態是正

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

3. 性能分析

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

圖1 演算法運行時間比較表

4. 結束語

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

[參 考 文 獻]

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

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

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

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

『貳』 學習演算法分析與設計需要那些基礎(是否需要學習離散數學和線性代數)

演算法分析與設計，目前國內本科生和碩士生的教材好像都是從國外翻譯過來的。聽起來挺復雜的樣子，如果簡單地掌握和運用還是不難的，大部分內容在數據結構中都涉及過，實際編程中也運用比較多，難的在於演算法的理論研究，如21世紀的七大難題之一的NP問題就是演算法問題（涉及邏輯可滿足性問題）。

簡單地講需要的基礎有以下幾類：
1、基礎類（相對一般本科生而言）：（1）把數據結構學好了演算法就不難的，而數據結構其實就是圖論的運用，如果是非數學專業的學生可以看離散數學中的圖論部分。（2）演算法分析設計時間和空間復雜度的計算，常用的還是毛澤東的戰略思想——以空間換取時間。所以要學會簡單的數量級運算，涉及部分代數式和數論的知識。只要簡單掌握運算就可以了，不必深究。
2、提高型（研究生水平）：圖論、組合數學、數理邏輯學要專門學習，可以採用數學系本科生的圖論、組合數學、數理邏輯學等專業課的教材。其中組合數學中的組合設計在一定程度上和演算法設計有異曲同工之處。
3、研究型（專業研究）：這主要看自己的研究方向了，如果研究能力強的話可以在很短時間內可以把需要遇到的數學知識搞懂，沒有現成的固定模式。其中如研究NP問題，需要非常精深的邏輯學知識和數論基礎。但不管哪個研究方向，數學的縝密思維和推理能力都是必備的，這不是一朝一夕可以練就的，需要長時間的鍛煉。

以上僅個人一點點體會，僅供參考。

『叄』 編譯原理和演算法分析與設計哪個更難

編譯原理和演算法分析與設計相比，演算法分析與設計更難。

演算法分析的話比較偏重整數規劃，數列的求解，組合數學等等，設計那就要靠悟性了，而且要見多識廣，不管你使用的是什麼語言，也不管語言怎麼發展，數據結構是變不了多少的。演算法設計也差不多，幫助你改善解決問題的思維。

演算法分析與設計的內容：

演算法設計與分析是整個CS課程體系當中最為重要的幾門課程之一，因為這門課是現代計算機科學發展的核心課程，和離散數學、數理邏輯四論地位相當，號稱必修中的必修，不過一般CS系不需要學數理邏輯四論，國內大學的四論教學開展的也不多。因此請大家一定要在這門課打好基礎，學好這門課能讓你未來的工作和學習非常輕松。

『肆』 《演算法分析與設計》課程講什麼內容

《演算法分析與設計》課程是理論性與應用性並重的專業課程。本課程以演算法設計策略為知識單元，系統地介紹計算機演算法的設計方法和分析技巧。課程教學主要內容包括：第一章，演算法概述；第二章，遞歸與分治策略；第三章，動態規劃；第四章，貪心演算法；第五章，回溯法；第六章，分支限界法。通過介紹經典以及實用演算法讓同學掌握演算法設計的基本方法。結合實例分析，讓同學深入理解演算法設計的技巧，以及分析演算法的能力。

『伍』 大學課程《演算法分析與設計》中動態規劃和貪心演算法的區別和聯系

對於，大學課程《演算法分析與設計》中動態規劃和貪心演算法的區別和聯系這個問題，首先要來聊聊他們的聯系：1、都是一種推導演算法；2、將它們分解為子問題求解，它們都需要有最優子結構。這兩個特徵師門的聯系。

拓展資料：

貪婪演算法是指在解決問題時，它總是在當前做出最佳選擇。也就是說，在不考慮全局優化的情況下，該演算法在某種意義上獲得了局部最優解。貪婪演算法不能得到所有問題的全局最優解。關鍵是貪婪策略的選擇。

動態規劃是運籌學的一個分支，是解決決策過程優化的過程。20世紀50年代初，美國數學家R·貝爾曼等人在研究多階段決策過程的最優化問題時，提出了著名的最優化原理，建立了動態規劃。動態規劃在工程技術、經濟、工業生產、軍事和自動控制等領域有著廣泛的應用，在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統可靠性問題上都取得了顯著的成果。