1 我要冒泡

???冒泡排序這個名字對于我們來說實(shí)在是過于熟悉了。作為一個程序員，如果敢說出自己不會冒泡排序，結(jié)局肯定是會被鄙視到火星上去。許多公司到學(xué)校去招聘應(yīng)屆畢業(yè)生的時候，都會要求寫一個冒泡排序。毫無疑問的，冒泡排序就是算法世界里面的HelloWorld。我選擇了一個弱智的開始，不外乎想告誡自己不要以非常弱智的方式結(jié)束自己的算法學(xué)習(xí)之旅。為了不使得自己的文章過于直白和缺乏技術(shù)含量，因此我加入了一些冒泡排序的改進(jìn)方法，并且給出了一個非常初級的效率評比方案。這一切的一切，不過是自我安慰而已，一點(diǎn)也不會改變本文菜鳥的本色。但是我還是老老實(shí)實(shí)地寫了這篇文章，希望一個好的開始，會帶來一個好的結(jié)束，而不是無行浪子的始亂終棄。

2?基本冒泡排序

???冒泡排序的基木思想:設(shè)想被排序的記錄數(shù)組d[1....N]垂直豎立.將每個記錄d[i]看作是一個氣泡，那么重的氣泡就會向下沉，輕的氣泡就會向上升。每次都是相鄰的兩個氣泡d[i]和d[i+1]進(jìn)行比較。如果d[i]>d[i+1]，那么就交換兩個氣泡，然后再比較d[i+1]和d[i+2]，以此類推，直到所有的氣泡都有序排列。假設(shè)有如下數(shù)據(jù)需要排序：20，37，11，42，29。

第一次冒泡：20?37 11 42 29
第二次冒泡：20?11?37 42 29
第三次冒泡：20?11?37?42 29
第四次冒泡：20?11?37?29 42

那么就找到了最重的氣泡42，接下來我們就可以按照同樣的辦法找到第二個氣泡，第三個氣泡，直到所有氣泡。

根據(jù)上面的分析，可以知道需要兩層循環(huán)。第一層循環(huán)控制次數(shù)，第二次循環(huán)控制要排序的數(shù)據(jù)范圍。如下所示：

第0次比較第0個到第n-1個，下標(biāo)控制0到n-2。
第1次比較第0個到第n-2個，下標(biāo)控制0到n-3。
.
.
第i次比較第0個到第n-i-1個，下標(biāo)控制0到n-i-2。
.
.
第n-2次比較第0個到第1個，下標(biāo)控制0到0。

算法如下：

????????///?<summary>
????????///?????冒泡排序的過程很簡單，首先將第一個記錄的關(guān)鍵字與第
????????///?????二個記錄的關(guān)鍵字進(jìn)行比較，若按升序排序，則當(dāng)?shù)谝粋€記錄的
????????///?????關(guān)鍵字大于第二個記錄的關(guān)鍵字時，將兩個記錄交換。然后再比
????????///?????較第二個記錄和第三個記錄的關(guān)鍵字。依次類推，直至第n-1個
????????///?????記錄和第n個記錄的關(guān)鍵字進(jìn)行比較為止。通過這樣的一趟冒
????????///?????泡排序，結(jié)果使得關(guān)鍵字最大的記錄被安置在最后一個記錄的位
????????///?????置上，即它的最終位置。接著進(jìn)行第二趟冒泡排序，對前n-1個
????????///?????記錄進(jìn)行同樣的操作，其結(jié)果是使關(guān)鍵字次大的記錄被安置到
????????///?????倒數(shù)第二個位置上。這樣，通過n一1趟冒泡排序，就將n-1個記
????????///?????錄安置到相應(yīng)的最終位置上，剩下的關(guān)鍵字最小的記錄就放在
????????///?????第一個位置，從而實(shí)現(xiàn)了升序排序。
????????///?</summary>
????????///?<param?name="myArray"></param>
????????public?static?void?BasicBubble(int?[]?myArray)
????????{
????????????for(int?i?=?0;?i?<?myArray.Length?-?1;?i++)??????????//循環(huán)的趟數(shù)
????????????{
????????????????for(int?j?=?0;?j?<?myArray.Length?-?1?-?i;?j++)//每趟循環(huán)的次數(shù)
????????????????{
????????????????????if(?myArray[j]?>?myArray[j+1]?)
????????????????????{
????????????????????????Swap(ref?myArray[i],?ref?myArray[i+1]);
????????????????????}
????????????????}
????????????}
????????}

交換數(shù)據(jù)是一個非常簡單的函數(shù)。在這兒寫出來也只是考慮本文的完整性而已。

????????private?static?void?Swap(ref?int?left,?ref?int?right)
????????{
????????????int?temp;

????????????temp?=?left;
????????????left?=?right;
????????????right?=temp;
????????}

基本冒泡排序的最好、最壞、平均情況下的時間復(fù)雜度都為O(n^2)。故算法的平均時間復(fù)雜度也為O(n^2)。但是若在某趟排序中未發(fā)現(xiàn)氣泡位置的交換，則說明待排序的無序區(qū)中所有氣泡均滿足輕者在上，重者在下的原則，即為正序。則冒泡排序過程可在此趟掃描后就終止。基于這種考慮，提出了第一種改進(jìn)的算法。

3?第一種改進(jìn)：不做無用功

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

????????///?<summary>
????????///?設(shè)置一個標(biāo)志位，當(dāng)沒有交換的時候這個標(biāo)志位不會變化，那么說明數(shù)據(jù)已經(jīng)
????????///?排序好了，就不需要再進(jìn)行剩余的循環(huán)。只有在標(biāo)志位被重新設(shè)置的情況下才會
????????///?進(jìn)行剩余的循環(huán)。
????????///?</summary>
????????///?<param?name="myArray"></param>
????????public?static?void?ImproveBubble1(int?[]?myArray)
????????{
????????????bool?isSorted?=?false;?

????????????for(int?i?=?0;?i?<?myArray.Length?-?1?&&?!isSorted;?i++)//只有在沒有排序的情況下才繼續(xù)循環(huán)
????????????{
????????????????isSorted?=?true;??????????????????????????????????????????????????????//設(shè)定排序標(biāo)志
????????????????for(int?j?=?0;?j?<?myArray.Length?-?1?-?i;?j++)
????????????????{
????????????????????if(?myArray[j]?>?myArray[j+1]?)
????????????????????{
????????????????????????isSorted?=?false;?????????????????????????????????????????????//如果是沒有排序，就重新設(shè)定標(biāo)志
????????????????????????Swap(ref?myArray[i],?ref?myArray[i+1]);
????????????????????}
????????????????}
????????????}
????????}

從這種算法可以看出.若記錄的初始狀態(tài)是正序（從小到大）的.則一趟掃描即可完成排序。所需的比較和記錄移動的次數(shù)分別達(dá)到最小值n- 1和0。即算法最好的時間復(fù)雜度為O(n)；若初始記錄是反序（從大到小）的.則需要進(jìn)行n-1趟排序，每趟排序要進(jìn)行n-i次關(guān)鍵宇的比較，且每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這情況下比較和移動次數(shù)達(dá)到最大值：

比較次數(shù)：Cmax= n(n-1)/2???????????????????????????移動次數(shù)： Mmax=3n(n-1)/2

因此這種改進(jìn)方法的最壞時間復(fù)雜度也為O(n^2)。在平均情況下.算法可能在中間的某一趟排序完后就終止，但總的比較次數(shù)仍為O(n^2).所以算法的平均時間復(fù)雜度為O(n^2)。因此，這種算法最好的時間復(fù)雜度為O(n)。平均，最壞時刻復(fù)雜度為O(n^2)。

4?第二種改進(jìn)：記錄犯罪現(xiàn)場

在冒泡排序的每趟掃描中，記住最后一次交換發(fā)生的位置lastexchange也能有所幫助。因?yàn)樵撐恢弥暗南噜徲涗浺呀?jīng)有序，故下一趟排序開始的時候，0到lastexchange已經(jīng)是有序的了，lastexchange到n-1是無序區(qū)。所以一趟排序可能使當(dāng)前有序區(qū)擴(kuò)充多個記錄.即較大縮小無序區(qū)范圍，而非遞減1，以此減少排序趟數(shù)。這種算法如下：

????????///?<summary>
????????///?????在冒泡排序中，每趟排序?qū)崿F(xiàn)了將最大(升序)或
????????///?????最小(降序)的記錄安置到未排序部分的最后位置，即最終位置。
????????///?????通過進(jìn)一步觀察研究，由于每趟排序過程中，通過和鄰記錄關(guān)鍵字兩兩
????????///?????比較，大(升序)或小(降序)的記錄在不斷地往下沉或往后靠，
????????///?????小(升序)或大(降序)的記錄在不斷往上冒或往前靠。
????????///?????每經(jīng)過一趟排序，在最后次交換位置后而的記錄都已經(jīng)排好序。根據(jù)
????????///?????上面的思路，對n個記錄進(jìn)行第k趟排序，首先需在第k-1趟排
????????///?????序時記下最后交換的位置。然后在第k趟排序時，將第一個記
????????///?????錄的關(guān)鍵字與第二個記錄的關(guān)鍵字進(jìn)行比較，符合交換條件時，
????????///?????進(jìn)行交換。再比較第二個記錄和第三個記錄的關(guān)鍵字，依次類
????????///?????推，直至第m-1個記錄和第m個記錄的關(guān)鍵字進(jìn)行比較，而不
????????///?????需要比較至n-k-1個記錄。在大部分排序中，m都小于n-k-1
????????///?????從而減少了比較趟數(shù)和每趟的比較次數(shù)。由于在第一趟排序時，
????????///?????沒有上一趟排序的m值。因此，還要設(shè)置m的初始值為n-1。
????????///?</summary>
????????///?<param?name="myArray"></param>
????????public?static?void?ImproveBubble2(int[]?myArray)
????????{
????????????int?m?=?myArray.Length?-?1;
????????????int?k,?j;

????????????while(?m?>?0?)
????????????{
????????????????for(?k=j=0;?j<m;?j++)
????????????????{
????????????????????if(?myArray[j]?>?myArray[j+1])
????????????????????{
????????????????????????Swap(ref?myArray[j],?ref?myArray[j+1]);
????????????????????????k?=?j;?//記錄每次交換的位置
????????????????????}
????????????????}
????????????????m?=?k;????????//記錄最后一個交換的位置
????????????}
????????}

從這種算法可以看出.若記錄的初始狀態(tài)是正序（從小到大）的.則一趟掃描即可完成排序.所需的關(guān)鍵比較和記錄移動的次數(shù)分別達(dá)到最小值n- 1和0。即算法最好的時間復(fù)雜度為O(n);若初始記錄是反序（從大到小）的.則需要進(jìn)行n-1趟排序.每趟排序要進(jìn)行n-i次關(guān)鍵宇的比較.且每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這情況下比較和移動次數(shù)達(dá)到最大值：

? 比較次數(shù)：Cmax= n(n-1)/2???????????????????????? 移動次數(shù) Mmax=3n(n-1)/2

因此.這種辦法的最壞時間復(fù)雜度也為O(n^2)。在平均情況下.算法較大地改變了無序區(qū)的范圍，從而減少了比較的次數(shù)，但總的比較次數(shù)仍為O(n^2).所以算法的平均時間復(fù)雜度為O(n^2)。因此.算法2最好的時間復(fù)雜度為O(n)。平均，最壞時刻復(fù)雜度為O(n^2)。

5?第三種改進(jìn)：雙向掃描，一網(wǎng)打盡

若記錄的初始狀態(tài)為:只有最輕的氣泡位于d[n]的位置(或者最重的氣泡位于d[0]位置).其余的氣泡均已排好序.在上述三種算法中都要做n-1趟掃描。實(shí)際上只需一趟掃描就可以完成排序。所以對于這種不對稱的情況。可對冒泡排序又作一次改進(jìn)。在排序過程中交替改變掃描方向.即先從下掃到上，再從上掃到下，來回地進(jìn)行掃描，這樣就得到雙向冒泡排序算法。

????????///?<summary>
????????///??對n個記錄進(jìn)行排序時，設(shè)up記錄了從前面向后面依次進(jìn)行掃描時最后的交換位置，
????????///??low記錄了從后面向前面依次進(jìn)行掃描時最前的交換位置。
????????///??由上個改進(jìn)的冒泡排序的原理可知，up后面的記錄和low前面的記錄都已有序。
????????///??每趟排序都由兩次不同方向的比較、交換組成。第一次是從未排好序的第一個記錄開始，
????????///??即從low記錄開始，向后依次兩兩比較，如果不符合條件，則交換之，
????????///??直至比較到未排好序的最后一個記錄，即up記錄為止。
????????///??同時記下最后一次交換的位置，并存于up。第二次是從未排好序的最后一個記錄開始,
????????///??即從up記錄開始，向前依次兩兩比較，如果不符合條件，則交換之，
????????///??直至比較到未排好序的第一個記錄，即low記錄為止。同時記下最后次交換的位置，
????????///??并存于low.?這樣，就完成了一趟排序。
????????///??每趟排序都實(shí)現(xiàn)了將未排好序部分的關(guān)鍵字大的記錄往后移(升序)，
????????///??關(guān)鍵字小的記錄往前移（升序)，從而使兩端已排好序（如果是降序，記錄移動的方向則相反)。
????????///??未排好序部分的記錄的首尾位置分別由low和up指明。
????????///??不斷按上面的方法進(jìn)行排序，使兩端已排好序的記錄不斷增多，
????????///??未排好序部分的記錄逐漸減少。即low和up的值不斷接近，當(dāng)low>=up時，
????????///??表明已沒有未排好序的記錄，排序就完成了。由于在第一趟排序時，
????????///??沒有上趟排序的low和up值。因此，還要設(shè)置low和up的初始值分別為0和n-1。
????????///?</summary>
????????///?<param?name="myArray"></param>
????????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;?i<up;?i++)????????//從上向下掃描
????????????????{
????????????????????if(myArray[i]>myArray[i+1])
????????????????????{
????????????????????????Swap(ref?myArray[i],?ref?myArray[i+1]);
????????????????????????index?=?i;?
????????????????????}
????????????????}

????????????????up?=?index;?????????????????????//記錄最后一個交換的位置
????????????????for(i=up;?i>low;?i--)?????????????//從最后一個交換位置處從下向上掃描
????????????????{
????????????????????if(myArray[i]<myArray[i-1])
????????????????????{
????????????????????????Swap(ref?myArray[i],?ref?myArray[i-1]);
????????????????????????index?=?i;
????????????????????}
????????????????}
????????????????low?=?index;????????????????????//記錄最后一個交換的位置
????????????}
????????}

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

6?實(shí)際測試

分別用隨機(jī)數(shù)生成器生成500，5000，20000個隨機(jī)的整數(shù)，然后排序。每種排序算法跑10次，取平均時間，可以在下表中看到運(yùn)行的時間。單位為毫秒。生成隨機(jī)數(shù)使用了.Net的Random類。

Random ran = new Random();
int?number?=?500;
int?[]?myArray?=?new?int[number];
for(int?i=0;?i<myArray.Length;?i++)
??????myArray[i]?=?ran.Next(0,?number);

	500隨機(jī)整數(shù)	5000隨機(jī)整數(shù)	20000隨機(jī)整數(shù)
基本排序方法	1.5625	145.3125	2428.125
改進(jìn)方法一	1.5625	139.0625	2279.6875
改進(jìn)方法二	?1.5625	134.375	2153.125
改進(jìn)方法三	?1.5625	104.6875	1651.5625

7?結(jié)論

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

/******************************************************************************************
?*【Author】：flyingbread
?*【Date】：2007年1月26日
?*【Notice】：
?*1、本文為原創(chuàng)技術(shù)文章，首發(fā)博客園個人站點(diǎn)(http://flyingbread.cnblogs.com/)，轉(zhuǎn)載和引用請注明作者及出處。
?*2、本文必須全文轉(zhuǎn)載和引用，任何組織和個人未授權(quán)不能修改任何內(nèi)容，并且未授權(quán)不可用于商業(yè)。
?*3、本聲明為文章一部分，轉(zhuǎn)載和引用必須包括在原文中。
?******************************************************************************************/

轉(zhuǎn)載于:https://www.cnblogs.com/FlyingBread/archive/2007/01/26/630674.html

總結(jié)

以上是生活随笔為你收集整理的排序1+1：冒泡排序法(BubbleSort)的改进以及效率比较的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。