冒泡排序的分析改進算法

《冒泡排序的分析改進算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、http://www.paper.edu.cn冒泡排序的分析改進算法楊義磊甘肅農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，蘭州（730070）Email：mailto:yangyilei001@126.com摘要：排序算法對于計算機信息處理很重要,一個好的排序不僅可以使信息查找的效率提高,而且還直接影響著計算機的工作效率。目前排序領(lǐng)域許多最簡單的算法都是基于冒泡排序算法,本文對冒泡排序的基本原理進行了介紹和分析,對算法性能進行了比較,并給出了相應(yīng)的改進算法.關(guān)鍵詞：排序算法，冒泡排序，算法分析，算法時間復(fù)雜度1.引言排序是計算機程序設(shè)計中的一種重要操作,它的功能是將一個數(shù)據(jù)元素(或記錄)的任意序列,重新

2、排列成一個按關(guān)鍵字有序的序列.排序是程序設(shè)計中非常重要的內(nèi)容,每一種程序設(shè)計語言中都涉及到排序,它的功能是將一組無序的的數(shù)據(jù)序列變成有序的數(shù)據(jù)序列,結(jié)果一般只有兩種情況:數(shù)據(jù)從大到小排列或者從小到大排列.排列的算法有很多種,常用的有三種,即冒泡排序,選擇排序,和插入排序.要判斷排序算法的優(yōu)劣,一般有兩個標(biāo)準(zhǔn):一是算法執(zhí)行所需要的時間,又稱時間復(fù)雜度;二是算法所需的存儲空間,又稱空間復(fù)雜度.排序算法的優(yōu)劣將直接影響到程序的性能.復(fù)雜度因排序算法的選擇而有所不同,一般可分為三類:(1)簡單的排序方法,其復(fù)雜度為[1]O(n2);(2)先進的排序方法,其時間復(fù)雜度為O(nlogn);(3)基數(shù)排

3、序,其時間復(fù)雜度為O(d*n).在計算機處理信息的過程中,由于排序數(shù)據(jù)或記錄非常頻繁,計算機運行時間的很大部分就被花費在數(shù)據(jù)或記錄的排序上.排序算法對于計算機信息處理很重要,一個好的排序不僅可以使信息查找的效率提高,而且還直接影響著計算機的工作效率。所以排序算法(sortingalgorithm)就成了計算機程序設(shè)計中的一個重要環(huán)節(jié),同時也成為研究的重要課題。它的功能是將一個數(shù)據(jù)元素(或記錄)的任意序列,重新排列成一個按關(guān)鍵字(keyword)排序的序列。在眾多的排序方法中,冒泡排序(bubblesort)是最簡單的一種,冒泡排序法可以形象的描述為:使較小的值象空氣泡一樣逐漸”上浮”到數(shù)組

4、的頂部,而較大的值逐漸”下沉”到[2]數(shù)組的底部.本文主要對冒泡排序算法及其幾種改進算法的基本原理進行介紹和分析.2.冒泡排序的基本思想冒泡排序是排序中一種簡單的排序方法.它的基本思想是對所有相鄰記錄關(guān)鍵字值進行比較,使較小的(大)關(guān)鍵字的記錄值往上升,這樣從上到下執(zhí)行一遍后,關(guān)鍵最大(小)的記錄沉到最底下.在下一遍掃描時,可以不考慮這個關(guān)鍵字最大(小)的記錄,而減少一次比較.上述的比較過程反復(fù)執(zhí)行,直到所有的記錄不再上升為止.此方法稱為下沉(上浮).冒泡排序算法的實現(xiàn)需兩重循環(huán),通常采用以下方法:外層循環(huán)控制變量(設(shè)為i)的變化是從數(shù)據(jù)比較的趟數(shù)考慮的.如:設(shè)有n個數(shù)據(jù)參加排序,需n-1

5、趟比較,i的變化范圍是1→n-1;而其內(nèi)層循環(huán)控制變量(設(shè)為j)的變化范圍為0→n-i-1(C語言中數(shù)組[3]元素下標(biāo)從0開始).3.冒泡排序的過程冒泡排序的過程很簡單.首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比-1-http://www.paper.edu.cn較,若為逆序(即L.r[1].key>L.r[2].key),則將兩個記錄交換之,然后比較第二個記錄和第三個記錄的關(guān)鍵字.依次類推,直至第n-1個記錄和第n個記錄的關(guān)鍵字進行過比較為止.上述過程稱做第一趟起泡排序,其結(jié)果使得關(guān)鍵字最大的記錄被安置到最后一個記錄的位置上.然后進行第二趟起泡排序,對前n-1個記錄進行同樣操作,

6、其結(jié)果是關(guān)鍵字次大的記錄被安置到第n-1個記錄的位置上.一般地,第i趟起泡排序是從L.r[1]到L.r[n-i+1]依次比較相鄰兩個記錄的關(guān)鍵字,并在”逆序”時交換相鄰記錄,其結(jié)果是這n-i+1個記錄中關(guān)鍵字最大的記錄被交換到第n-i+1個位置上.整個排序過程需進行k(1≤k

7、91327276565651327383897761327494976132749ˉ49ˉ132749ˉ652749ˉ7649ˉ97初第第第第第第始一二三四五六關(guān)趟趟趟趟趟趟鍵排排排排排排字序序序序序序后后后后后后圖1起泡排序示例分析起泡排序的效率,容易看出,若初始序列為”正序”序列,則只需進行一趟排序,在排序過程中進行n-1次關(guān)鍵字間的比較,且不移動記錄;反之,若初始序列為”逆序”序列,則需進行n-1趟排序,需進行2∑