简单的冒泡算法，原来不简单
是不是觉得冒泡算法很简单？
是的，确实很简单，中心思想是两两交换。
那你能写出冒泡算法吗？
你能解释冒泡算法中的各层含义是什么吗？
你又能写出几种冒泡算法呢？
曾经在面试中，遇到过冒泡算法，我能模糊的写出，却纠结于参数边界值的控制。为了不再继续模糊下去，为了不至于被人鄙视----硕士毕业3年了，连这个小算法也搞不好。
于是趁此离职时期，好好的分析一下。
通常为
for (int i=0;i
或
For(int i=1;i
当然，如果你喜欢，你甚至可以定义i初始值为3、为4、为100等。不过我相信，没人会那么无聊的。
不过这却揭示了第一层循环与i的初始值无关，而只与循环了多少次有关。
因此，冒泡排序第一层循环的含义为：需要遍历多次数组，才能将这个数组排好序。
那到底需要遍历多少次数组，才能排好序呢？
第一次遍历，确定一个最值。
第二次遍历，确定第二个最值。
。。。
第num-1次遍历，确定第num-1最值。Num-1个最值都确定了，自然整个数组也就排好序了。
因此，第一层循环含义为：需要遍历num-1次数组，才能将数组排好序。
通常定义为int j; j是一个与i相关的变量，第2层循环需要用到第一层的i的值。
那第二层循环要解决的问题是什么？
不好想的话，我们反过来想，在第二层循环时，我们还要对已经排好序的位置进行遍历吗？
当然不需要作此无用功，在第二层遍历中，我们只需对未排好序的那些待排位置进行遍历即可，而首先，我们必须知道，哪些元素是已经拍过序的，哪些元素是待排序的。
所以，我们第二层循环要解决的问题便是：待排序区域的起始和结尾位置。
而要解决这个问题，
首先，第一个要解决的便是：在进行这个循环时，数组已经排好了几个值。
其次，第二个要解决的便是：在数组中，待排序区域的其实和末尾位置分别是什么。
第一个要解决的问题与第一层循环已经进行了多少次有关。
第二个要解决的问题则与排序时遍历的方向有关。
[cpp]view plaincopy
voidBubbleSortBtoS(intA[],intnum)// 从数组末尾向数组开始遍历
{
inttemp=0;
for(inti=0;i
{
for(intj=num-1;j>i;j--)// 待排的数据为i,i+1,...num-1 此处判断条件为j>i
{
if(A[j]
{
temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
}
}
}
}
[cpp]view plaincopy
voidBubbleSortStoB(intA[],intnum)// 从数组开始向数组末尾遍历
{
inttemp=0;
for(inti=0;i
{
for(intj=0;j
{
if(A[j]>A[j+1])
{
temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
}
}
好吧，总有人喜欢从i=1开始作为第一层循环的起始值，这是习惯问题，因此我们也分析下从1开始时的程序。
[cpp]view plaincopy
voidBubbleSortBtoS1(intA[],intnum)// 从数组末尾向数组开始遍历
{
inttemp=0;
for(inti=1;i
{
for(intj=num-1;j>=i;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;
}
}
}
}
[cpp]view plaincopy
voidBubbleSortStoB1(intA[],intnum)// 从数组开始向数组末尾遍历
{
inttemp=0;
for(inti=1;i
{
for(intj=0;j<=num-i-1;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;
}
}
}
}
[cpp]view plaincopy
voidBubbleSortStoB_Tail(intA[],intnum)// tail参数记录末尾位置
{
inttemp=0;
inttail=num-1;
for(inti=0;i
{
for(intj=0;j
{
if(A[j]>A[j+1])
{
temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
tail--;
}
}
[cpp]view plaincopy
voidBubbleSortBtoS_Modify(intA[],intnum)// 从数组末尾向数组开始遍历
{
boolbSwap=false;
inttemp=0;
for(inti=0;i
{
for(intj=num-1;j>i;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)// 设置是否交换标志以提前退出
{
break;
}
}
}
[cpp]view plaincopy
voidCockTail(intA[],intnum)
{
inttail=num-1;
inttemp=0;
for(inti=0;i
{
for(intj=tail;j>i;j--)
{
if(A[j]
{
temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
}
}
i++;
for(intj=i;j
{
if(A[j]>A[j+1])
{
temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
tail--;
}
}
