1.1第一層循環(huán)
通常為
for (int i=0;i
或
For(int i=1;i
當(dāng)然，如果你喜歡，你甚至可以定義i初始值為3、為4、為100等。不過我相信，沒人會(huì)那么無聊的。
不過這卻揭示了第一層循環(huán)與i的初始值無關(guān)，而只與循環(huán)了多少次有關(guān)。
因此，冒泡排序第一層循環(huán)的含義為：需要遍歷多次數(shù)組，才能將這個(gè)數(shù)組排好序。
那到底需要遍歷多少次數(shù)組，才能排好序呢？
第一次遍歷，確定一個(gè)最值。
第二次遍歷，確定第二個(gè)最值。
。。。
第num-1次遍歷，確定第num-1最值。
Num-1個(gè)最值都確定了，自然整個(gè)數(shù)組也就排好序了。
因此，第一層循環(huán)含義為：需要遍歷num-1次數(shù)組，才能將數(shù)組排好序。
1.2第二層循環(huán)
通常定義為int j;
j是一個(gè)與i相關(guān)的變量，第2層循環(huán)需要用到第一層的i的值。
那第二層循環(huán)要解決的問題是什么？
不好想的話，我們反過來想，在第二層循環(huán)時(shí)，我們還要對(duì)已經(jīng)排好序的位置進(jìn)行遍歷嗎？
當(dāng)然不需要作此無用功，在第二層遍歷中，我們只需對(duì)未排好序的那些待排位置進(jìn)行遍歷即可，而首先，我們必須知道，哪些元素是已經(jīng)拍過序的，哪些元素是待排序的。
所以，我們第二層循環(huán)要解決的問題便是：待排序區(qū)域的起始和結(jié)尾位置。
而要解決這個(gè)問題，
首先，第一個(gè)要解決的便是：在進(jìn)行這個(gè)循環(huán)時(shí)，數(shù)組已經(jīng)排好了幾個(gè)值。
其次，第二個(gè)要解決的便是：在數(shù)組中，待排序區(qū)域的其實(shí)和末尾位置分別是什么。
第一個(gè)要解決的問題與第一層循環(huán)已經(jīng)進(jìn)行了多少次有關(guān)。
第二個(gè)要解決的問題則與排序時(shí)遍歷的方向有關(guān)。
2 冒泡排序算法
2.1
i=0
-
void BubbleSortBtoS(int A[],int num) // 從數(shù)組末尾向數(shù)組開始遍歷
-
{
-
-
int temp=0;
-
for (int i=0;i
-
{
-
-
for (int j=num-1;j>i;j--) // 待排的數(shù)據(jù)為i,i+1,...num-1 此處判斷條件為j>i
-
{
-
if (A[j]
-
{
-
temp=A[j];
-
A[j]=A[j-1];
-
A[j-1]=temp;
-
}
-
}
-
}
-
-
}
-
void BubbleSortStoB(int A[],int num) // 從數(shù)組開始向數(shù)組末尾遍歷
-
{
-
-
int temp=0;
-
for (int i=0;i
-
{
-
-
for (int j=0;j// 待排的數(shù)據(jù)為0,1,2,...,n-i-1 此處判斷條件為j
-
{
-
if (A[j]>A[j+1])
-
{
-
temp=A[j];
-
A[j]=A[j+1];
-
A[j+1]=temp;
-
}
-
}
-
}
-
-
}
2.2
i=1
好吧，總有人喜歡從i=1開始作為第一層循環(huán)的起始值，這是習(xí)慣問題，因此我們也分析下從1開始時(shí)的程序。
-
void BubbleSortBtoS1(int A[],int num) // 從數(shù)組末尾向數(shù)組開始遍歷
-
{
-
-
int temp=0;
-
for (int i=1;i
-
{
-
-
for (int j=num-1;j>=i;j--) // 待排的數(shù)據(jù)為i-1,i,i+1,...num-1 此處為j>=i
-
{
-
if (A[j]
-
{
-
temp=A[j];
-
A[j]=A[j-1];
-
A[j-1]=temp;
-
}
-
}
-
}
-
-
}
-
void BubbleSortStoB1(int A[],int num) // 從數(shù)組開始向數(shù)組末尾遍歷
-
{
-
-
int temp=0;
-
for (int i=1;i
-
{
-
-
for (int j=0;j<=num-i-1;j++) // 待排的數(shù)據(jù)為0,1,2,...,n-i-1,n-i 此處為j<=num-i-1
-
{
-
if (A[j]>A[j+1])
-
{
-
temp=A[j];
-
A[j]=A[j+1];
-
A[j+1]=temp;
-
}
-
}
-
}
-
-
}
3 冒泡算法的小改進(jìn)
3.1 簡化從前往后遍歷
-
void BubbleSortStoB_Tail(int A[],int num) // tail參數(shù)記錄末尾位置
-
{
-
-
int temp=0;
-
int tail=num-1;
-
for (int i=0;i
-
{
-
-
for (int j=0;j// 待排的數(shù)據(jù)為0,1,2,...,tail 實(shí)則tail==num-i-1
-
{
-
if (A[j]>A[j+1])
-
{
-
temp=A[j];
-
A[j]=A[j+1];
-
A[j+1]=temp;
-
}
-
}
-
-
tail--;
-
}
-
-
}
3.2 增設(shè)是否有序標(biāo)志
-
void BubbleSortBtoS_Modify(int A[],int num) // 從數(shù)組末尾向數(shù)組開始遍歷
-
{
-
-
bool bSwap=false;
-
int temp=0;
-
for (int i=0;i
-
{
-
-
for (int j=num-1;j>i;j--) // 待排的數(shù)據(jù)為i,i+1,...num-1 此處判斷條件為j>i
-
{
-
if (A[j]
-
{
-
bSwap=true;
-
temp=A[j];
-
A[j]=A[j-1];
-
A[j-1]=temp;
-
}
-
}
-
-
if (!bSwap) // 設(shè)置是否交換標(biāo)志以提前退出
-
{
-
break;
-
}
-
}
-
-
}
4 雞尾酒算法
-
void CockTail(int A[],int num)
-
{
-
-
int tail=num-1;
-
-
int temp=0;
-
-
for (int i=0;i
-
{
-
-
for (int j=tail;j>i;j--)
-
{
-
if (A[j]
-
{
-
temp=A[j];
-
A[j]=A[j-1];
-
A[j-1]=temp;
-
-
}
-
}
-
-
i++;
-
-
-
for (int j=i;j
-
{
-
if (A[j]>A[j+1])
-
{
-
temp=A[j];
-
A[j]=A[j+1];
-
A[j+1]=temp;
-
}
-
}
-
tail--;
-
}
-
-
}
|
