冒泡排序是非常容易理解和實現,以從小到大排序舉例:
設數組長度為N。
1.比較相鄰的前後二個數據,如果前面數據大於後面的數據,就將二個數據交換。
2.這樣對數組的第0個數據到N-1個數據進行一次遍歷後,最大的一個數據就“沉”到數組第N-1個位置。
3.N=N-1,如果N不為0就重復前面二步,否則排序完成。
按照定義很容易寫出代碼:
//冒泡排序1
void BubbleSort1(int a[], int n)
{
int i, j;
for (i = 0; i < n; i++)
for (j = 1; j < n - i; j++)
if (a[j - 1] > a[j])
Swap(a[j - 1], a[j]);
}
下面對其進行優化,設置一個標志,如果這一趟發生了交換,則為true,否則為false。明顯如果有一趟沒有發生交換,說明排序已經完成。
//冒泡排序2
void BubbleSort2(int a[], int n)
{
int j, k;
bool flag;
k = n;
flag = true;
while (flag)
{
flag = false;
for (j = 1; j < k; j++)
if (a[j - 1] > a[j])
{
Swap(a[j - 1], a[j]);
flag = true;
}
k--;
}
}
再做進一步的優化。如果有100個數的數組,僅前面10個無序,後面90個都已排好序且都大於前面10個數字,那麼在第一趟遍歷後,最後發生交換的位置必定小於10,且這個位置之後的數據必定已經有序了,記錄下這位置,第二次只要從數組頭部遍歷到這個位置就可以了。
//冒泡排序3
void BubbleSort3(int a[], int n)
{
int j, k;
int flag;
flag = n;
while (flag > 0)
{
k = flag;
flag = 0;
for (j = 1; j < k; j++)
if (a[j - 1] > a[j])
{
Swap(a[j - 1], a[j]);
flag = j;
}
}
}
冒泡排序畢竟是一種效率低下的排序方法,在數據規模很小時,可以采用。數據規模比較大時,最好用其它排序方法。
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