冒泡排序算法,是最基本的排序算法, 它屬於交換排序。
冒泡排序過程
設想被排序的數組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;
}
}
}
}