一 、算法介紹
（1）算法概述
排序算法有很多伏嗜，其中最簡單直接的就是冒泡啦坛悉。冒泡排序（Bubble Sort）是一種典型的交換排序通過交換數(shù)據(jù)元素的位置進(jìn)行排序伐厌。這個算法的名字由來是因?yàn)樵酱蟮脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端，故名裸影。
（2）算法原理
- 比較相鄰的元素挣轨。如果第一個比第二個大，就交換他們兩個轩猩。
- 對每一對相鄰元素作同樣的工作卷扮，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)均践，最后的元素應(yīng)該會是最大的數(shù)画饥。
- 針對所有的元素重復(fù)以上的步驟，除了最后一個浊猾。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較热鞍。
（3）算法分析
時間復(fù)雜度
-
若文件的初始狀態(tài)是正序的葫慎，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)C 和記錄移動次數(shù)M均達(dá)到最小值所以薇宠，冒泡排序最好的[時間復(fù)雜度
-
若初始文件是反序的，需要進(jìn)行 n-1 趟排序澄港。每趟排序要進(jìn)行n-i
次關(guān)鍵字的比較(1≤i≤n-1)椒涯，且每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這種情況下回梧，比較和移動次數(shù)均達(dá)到最大值
冒泡排序的最壞時間復(fù)雜度為綜上废岂，因此冒泡排序總的平均時間復(fù)雜度為
算法穩(wěn)定性
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較狱意，交換也發(fā)生在這兩個元素之間湖苞。所以，如果兩個元素相等详囤，我想你是不會再無聊地把他們倆交換一下的财骨；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來藏姐，這時候也不會交換隆箩，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法羔杨。
二 捌臊、算法描述
#include <stdio.h>
#define SIZE 8
void bubble_sort(int a[], int n);
void bubble_sort(int a[], int n)
{
int i, j, temp;
for (j = 0; j < n - 1; j++)
for (i = 0; i < n - 1 - j; i++)
{
if(a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
int main()
{
int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
int i;
bubble_sort(number, SIZE);
for (i = 0; i < SIZE; i++)
{
printf("%d", number[i]);
}
printf("\n");
}
結(jié)果：12 15 24 45 51 78 84 95
本文參考自百度百科，歡迎指正问畅。
