[演算法] 泡沫排序法
泡沬排序法，是依序判斷每個數字，每次判斷之最大數會移到最上方，如泡泡一般，稱為泡沫排序法(Bubble Sort)。
例：
２ １２ ８ ７ ３９ １
泡沬排序法：
[第一次]
２ １２ ８ ７ ３９ １ ( ２是否比１２大，否，下一位 )
２ １２ ８ ７ ３９ １ ( １２是否比８大，是，交換，下一位 )
２ ８ １２ ７ ３９ １ ( １２是否比７大，是，交換，下一位 )
２ ８ ７ １２ ３９ １ ( １２是否比３９大，否，下一位 )
２ ８ ７ １２ ３９ １ ( ３９是否比１大，是，交換)
２ ８ ７ １２ １ ３９ ( 結果)
第一次排完後，３９即被移到最右方，接著再進行第二次排序
２ ８ ７ １２ １ ３９ ( ２是否比８大，否，下一位 )
２ ８ ７ １２ １ ３９ ( ８是否比７大，是，交換，下一位 )
２ ７ ８ １２ １ ３９ ( ８是否比１２大，否，下一位 )
２ ７ ８ １２ １ ３９ ( １２是否比１大，是，交換 )
２ ７ ８ １ １２ ３９ ( 結果)
第二次排完後，１２被移到最右方第二位，接下來一直進行排到全部換完為止。
提早結束事件
當某一次排序時完全沒發生交換的事件則代表其實已經全部都排列完成了。
例：
２ １２ ２５ ２０
泡沬排序法：
[第一次]
２ １２ ２５ ２０ ( ２是否比１２大，否，下一位 )
２ １２ ２５ ２０ ( １２是否比２５大，否，下一位 )
２ １２ ２５ ２０ ( ２５是否比２０大，是，交換)
２ １２ ２０ ２５ ( 結果)
進行第二次排序時，會發現沒有發生任何交換事件，因此可提早結束排序。
程式範例（ Linux C ）：
#include
//---Env define---//
#include
#include
#include
#include
typedef
enum Boolean{
false, true
} bool;
/*************************************************************************/
/*! \struct Leo_bubble
* \brief Leo_bubble function,IN: InputData Input_Number,OUT: None
* \details Leo_bubble function \n
* \author Leo Cheng
*/
/*************************************************************************/
int
Leo_bubble(int*
InputData,int
Input_Number)
{
int i,j;
int Buffer = 0;
int
AnswerNumber[Input_Number];
bool EarlyEnd =
true;
//---Save Input Data to AnswerNumber, and show
InputData---//
for( i=0 ; i
{
AnswerNumber[i] = *(InputData+i);
printf("%d ",AnswerNumber[i]);
}
printf("\n");
//---Start Bubble Sort---//
for( i=0 ; i
{
EarlyEnd = true;
for( j=0 ; j
{
//--Move j to J+1---//
if(AnswerNumber[j]
> AnswerNumber[j+1])
{
Buffer = AnswerNumber[j+1];
AnswerNumber[j+1] =
AnswerNumber[j];
AnswerNumber[j] = Buffer;
EarlyEnd = false;
}
}
//--Not to move j to j+1 in this time, it's
mean all finish---//
if( EarlyEnd ==
true )
{
break;
}
}
//---Show the answers---//
for( i=0 ; i
{
printf("%d ",AnswerNumber[i]);
}
printf("\n");
}
/*************************************************************************/
/*! \struct main
* \brief main function,IN: None,OUT: None
* \details main function \n
* \author Leo Cheng
*/
/*************************************************************************/
void main()
{
int Input_Number = 10;
int
InputData[Input_Number];
int i;
srand(time(NULL));
for( i=0 ; i
{
InputData[i]=(rand()%100)+1;
}
Leo_bubble(InputData,Input_Number);
}
留言列表
