9.2.1冒泡排序Bubble Sort)
冒泡排序是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關鍵字，如果他們順序錯誤就把他們交換過來。這個算法的名字由來是由於越小的元素會經過交換慢慢浮到數列的頂端。
1、冒泡排序初級版
#include <stdio.h>
#include <stdlib.h>
void BubbleSort(int arr[], int n)
{
int i;
int j;
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
int temp;
if(arr[i] > arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
void print(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int main()
{
int arr[]={9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前：\n");
print(arr, n);
BubbleSort(arr, n);
printf("排序後：\n");
print(arr, n);
system("pause");
return 0;
}
這段代碼不是標准的冒泡排序算法，因為它不滿足“兩兩比較相鄰記錄”的冒牌排序思想，它是最簡單的交換的排序而已。
思路：讓第1個位置的關鍵字和它後面的每一個關鍵字依次比較，如果大則交換，這樣第1個位置的關鍵字在一次循環後一定變成最小值。不再搭理第一個位置了，讓第2個位置的關鍵字和它後面的每一個關鍵字依次比較，如果打則交換，這樣第2個位置的關鍵字在一次循環後一定變成次最小值。依次循環，直到所有關鍵字排序完成。
需要比較的次數：n-1) + (n-2) + ...... + 2 + 1 = n(n-1)/2;
可能的最大交換次數：n-1) + (n-2) + ...... + 2 + 1 = n(n-1)/2;
2、冒泡排序正宗版
#include <stdio.h>
#include <stdlib.h>
void BubbleSort(int arr[], int n)
{
int i;
int j;
for(i=0; i<n; i++)
{
// for(j=n-2; j>=i; j--) //一次循環後，最小的到漂浮到最上面。
for(j=0; j<n-1-i; j++) //一次循環後，最大的到沉到最下面。
{
int temp;
if(arr[j+1] < arr[j])
{
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
}
void print(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int main()
{
int arr[]={9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前：\n");
print(arr, n);
BubbleSort(arr, n);
printf("排序後：\n");
print(arr, n);
system("pause");
return 0;
}
經過一次循環後，最小的數據如同氣泡般慢慢浮到上面，因此成為冒泡排序。
或者 最大的數據慢慢沉到下面，也可以叫冒泡排序。
//for(j=n-2;j>=i; j--)//一次循環後，最小的到漂浮到最上面。
//for(j=0;j<n-1-i; j++) //一次循環後，最大的到沉到最下面。
需要比較的次數：n-1) + (n-2) + ...... + 2 + 1 =n(n-1)/2;
可能的最大交換次數：n-1) + (n-2) + ...... + 2 + 1 =n(n-1)/2;
3、冒泡排序優化算法
如果進行一次循環後，沒有任何數據進行交換，則說明此序列已經有序，無需再進行後面的循環判斷了。
#include <stdio.h>
#include <stdlib.h>
void BubbleSort(int arr[], int n)
{
int i;
int j;
bool flag = true; //優化算法
for(i=0; i<n && flag; i++) //優化算法
{
flag = false; //優化算法
// for(j=n-2; j>=i; j--) //一次循環後，最小的到漂浮到最上面。
for(j=0; j<n-1-i; j++) //一次循環後，最大的到沉到最下面。
{
int temp;
if(arr[j+1] < arr[j])
{
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
flag = true; //優化算法
}
}
}
}
void print(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int main()
{
int arr[]={9, 1, 5, 8, 3, 7, 4, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前：\n");
print(arr, n);
BubbleSort(arr, n);
printf("排序後：\n");
print(arr, n);
system("pause");
return 0;
}
優化算法可以避免在已經有序的情況下進行無意義的循環判斷
4 、冒泡排序復雜度分析
對優化後的代碼分析，若排序的本身是正序排列從小到大排列），則只需做n-1次比較，無需交換最好情況）。若本身為反序排列從大到小排列），則需做n(n-1)/2次比較，而且需做n(n-1)/2次交換最壞情況）。
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282068
