感謝 @向陽_只為一束光 在留言板中指出文章錯誤。
冒泡排序是排序算法的一種，思路清晰，代碼簡潔，常被用在大學生計算機課程中。
“冒泡”這個名字的由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，故名。
這裡以從小到大排序為例進行講解。
基本思想及舉例說明
冒泡排序的基本思想就是不斷比較相鄰的兩個數，讓較大的元素不斷地往後移。經過一輪比較，就選出最大的數；經過第2輪比較，就選出次大的數，以此類推。
下面以對 3 2 4 1 進行冒泡排序說明。
第一輪 排序過程
3 2 4 1 （最初）
2 3 4 2 （比較3和2，交換）
2 3 4 1 （比較3和4，不交換）
2 3 1 4 （比較4和1，交換）
第一輪結束，最大的數4已經在最後面，因此第二輪排序只需要對前面三個數進行再比較。
第二輪 排序過程
2 3 1 4 （第一輪排序結果）
2 3 1 4 （比較2和3，不交換）
2 1 3 4 （比較3和1，交換
第二輪結束，第二大的數已經排在倒數第二個位置，所以第三輪只需要比較前兩個元素。
第三輪 排序過程
2 1 3 4 （第二輪排序結果）
1 2 3 4 （比較2和1，交換）
至此，排序結束。
算法總結及實現
對於具有N個元素的數組R[n]，進行最多N-1輪比較；
第一輪，逐個比較（R[1], R[2]）, （R[2], R[3]）, （R[3], R[4]）, ……. （R[N-1], R[N]） ; 最大的元素會被移動到R[N]上。
第二輪，逐個比較（R[1], R[2]）, （R[2], R[3]）, （R[3], R[4]）, ……. （R[N-2], R[N-1]）；第二大元素會被移動到R[N-1]上。
。。。。
以此類推，直到整個數組從小到大排序。
下面給出了冒泡排序的一般實現和優化實現。一般實現是教科書裡常見的實現方法，無論數組是否排序好了，都會進行N-1輪比較； 而優化實現，在數組已經排序好的情況下，會提前退出比較，減小了算法的時間復雜度。
#include<stdio.h>
#include<stdlib.h>
#define N 8
void bubble_sort(int a[],int n);
//一般實現
void bubble_sort(int a[],int n)//n為數組a的元素個數
{
//一定進行N-1輪比較
for(int i=0; i<n-1; i++)
{
//每一輪比較前n-1-i個，即已排序好的最後i個不用比較
for(int j=0; j<n-1-i; j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1]=temp;
}
}
}
}
//優化實現
void bubble_sort_better(int a[],int n)//n為數組a的元素個數
{
//最多進行N-1輪比較
for(int i=0; i<n-1; i++)
{
bool isSorted = true;
//每一輪比較前n-1-i個，即已排序好的最後i個不用比較
for(int j=0; j<n-1-i; j++)
{
if(a[j] > a[j+1])
{
isSorted = false;
int temp = a[j];
a[j] = a[j+1];
a[j+1]=temp;
}
}
if(isSorted) break; //如果沒有發生交換，說明數組已經排序好了
}
}
int main()
{
int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
bubble_sort(num, N); //或者使用bubble_sort_better(num, N);
for(int i=0; i<N; i++)
printf("%d ", num[i]);
printf("\n");
system("pause");
return 0;
}
