冒泡排序作為最經典的算法，雖然對大數據無用武之地。但是對於少量的數據，我們用冒泡排序，在時間復雜度上也是可以接受的，又因為它實現起來比較簡單，所以也經常的被人們使用。並且可以通過一些方法來改進最原始的冒泡排序，這種改進算法的思路也有可取之處。
前一兩天參加宜搜科技的筆試，就考到了冒泡排序。我當時就想寫一個改進之後的算法。還是稍稍的考慮了一下的。所以現在整理一下，希望下次會更加的熟練。
冒泡排序的思路非常的簡單，即將相鄰的兩個數相比較，將較大的數向後移動。我們可以知道每一次都會有一個大數沉底。
下面我們來看最簡單的冒泡排序：
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
//未改進的冒泡排序，其時間復雜度為O(n*n)
void bubble1(int a[],int n)
{
for(int i=0;i<n;i++)
for(int j=1;j<n-i;j++)
if(a[j-1]>a[j])
swap(a[j-1],a[j]);
}
我們稍微的思考一下，就可以找到一種改進方法。如果在一趟排序中沒有數據發生交換，那不就是說，數據已經有序了嗎。據此很容易寫出以下的代碼:
void bubble2(int a[],int n)
{
int k=n;
bool flag=true;
while(flag)
{
flag=false;
for(int i=1;i<k;i++)
{
if(a[i-1]>a[i]){
swap(a[i-1],a[i]);
flag=true;
}
}
k--;
}
}
還能改進嗎？我們可以通過記錄每趟發生交換的最後位置(後面的都已經有序了)，來縮小需要比較的數組長度。據此，容易寫出以下的代碼：
//在這個基礎之上還是繼續改進算法的
//我們可以通過記錄每一趟排序最後發生交換的位置來縮小比較數組的大小
//這樣，雖然改進比較小，但是思路非常的巧妙
void bubble3(int a[],int n)
{
int flag=n;
int k;
while(flag>0)
{
k=flag;
//將flag置零，這樣是為了使程序能夠安全的跳出，而非死循環
flag=0;
for(int i=1;i<k;i++)
{
if(a[i-1]>a[i])
swap(a[i-1],a[i]);
flag=i;
}
}
}
void printArray(int a[],int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
好了，這時這些了。如果大家有更好的方法或者思路，不吝指教。
PHP 冒泡排序法 http://www.linuxidc.com/Linux/2014-08/105971.htm
經典排序之冒泡排序 http://www.linuxidc.com/Linux/2014-07/104762.htm
Python實現冒泡排序法 http://www.linuxidc.com/Linux/2014-06/103897.htm
Go語言實現冒泡排序 http://www.linuxidc.com/Linux/2014-06/103844.htm
C++ 使用模板實現冒泡排序 http://www.linuxidc.com/Linux/2014-02/96914.htm
Java簡單排序之冒泡排序代碼 http://www.linuxidc.com/Linux/2013-11/92782.htm
冒泡排序優化版,性能近乎翻倍 http://www.linuxidc.com/Linux/2013-09/90710.htm