起泡法

起泡法是從一端開始比較的，第一次循環就是把最大數放到最後一個位置，第二次循環就是把第二最大數放到倒數第二位置。整個過程就像燒開水一樣，較小值像水中的氣泡一樣逐趟往上冒，每一趟都有一塊“最大”的石頭沉到水底。

如此循環實現數據的排序。下面舉一個用起泡法對n個數字進行排序的例子：

#include<stdio.h>

void main()

{

int a[100];

int n,i,j,t;

printf("請輸入要排序的數字個數:");

scanf("%d",&n);

printf("請輸入各個數字:");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

printf("\n");

for(j=0;j<(n-1);j++) /*進行n-1次循環，實現n-1趟比較*/

for(i=0;i<(n-1-j);i++) /*在每一趟中進行n-1-j次比較*/

if(a[i]>a[i+1]) /*相鄰兩個數比較*/

{t=a[i];a[i]=a[i+1];a[i+1]=t;}

printf("經過排序後的數字為:");

for(i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n");

}

那么我們是否可以找到最小數的同時找到最大數呢？當然可以。方法是在一端起泡時同時在另一端也進行起泡。即反向起泡。下面的程式段實現的是雙向起泡：

void Bubble2Sort(int* pData,int Count)

{

int temp;

int left = 1;

int right =Count -1;

int t;

do

{

//正向的部分

for(int i=right;i>=left;i--)

{

if(pData {

iTemp = pData;

pData = pData[i-1];

pData[i-1] = iTemp;

t = i;

}

}

left = t+1;

//反向的部分

for(i=left;i {

if(pData {

iTemp = pData;

pData = pData[i-1];

pData[i-1] = iTemp;

t = i;

}

}

right = t-1;

}while(left<=right);

}

分析上面的程式段我們可以發現正向起泡時第一次循環找出了最小數，反向起泡第一次循環找到最大數。很顯然在一次循環中即可以找到一個最小的數還可以找到一個最大的數，所以用雙向冒泡排序的交換的次數減少了，從而達到了最佳化起泡法的作用。