改進的冒泡排序算法

冒泡排序算法，是最基本的排序算法， 它屬於交換排序。

冒泡排序過程

設想被排序的數組R[1..N]垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"（交換位置），如此反復進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。

性能分析

若記錄序列的初始狀態為"正序"，則冒泡排序過程只需進行一趟排序，在排序過程中只需進行n-1次比較，且不移動記錄；反之，若記錄序列的初始狀態為"逆序"，則需進行n(n-1）/2次比較和記錄移動。因此冒泡排序總的時間復雜度為O(n*n)。

冒泡排序實現

根據掃描方向不同，實現略有不同。

代碼如下：

void BubbleSort_1(int a[], int size)
{
for (int i = 0; i < size -1; i++)
{
for (int j = size - 1; j > i ; j--)
{
if (a[j-1] > a[j])
{
int temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}