排序算法系列2——冒泡排序
冒泡排序1.0
这是最容易理解的交换排序的思想,不是真正的冒泡排序,因为它不是利用两两比较临近数字的大小得出结果,而是拿要确定的位置的数字与后边各个数字相比较,确定大当家的位置就要让待选的大当家和后边的小喽啰都比试一番,谁赢了就换,二当家也是如此出来的,依次排列。比如对1,5,3,2,6进行从从小到大升序输出
那么第一轮就是比较1和5的大小,由于1<5,则1和5不用交换,然后再让1和3比较一直到和6比较,一轮下来,就可以保证第一个位置是最小的了
第二轮就从5开始,分别和后边的3,2,6进行比较,5先和3交换,3再和2交换,最后第二轮定下来前两个位置最小,以此类推
void BubbleSort1(SqList *L)//从小到大排序
{
int i,j;
for(i=1;i<L->length;i++)
{
for(j=i+1;j<=L->length;j++)
{
if(L->r[i]>L->r[j])
{
swap(L,i,j);
}
}
}
}
冒泡排序2.0
通过冒泡排序1.0我们不难发现,每次遍历一次数组只能从待排序的位置里找出一个确定值,而待排序的数互相之间并没有简单排序,造成资源浪费。真正的冒泡算法是两两比较临近数字的大小,每一次遍历待排序的数组都会由比较有简单的排序
比如1,5,3,2,6
第一轮
6和2比较,由于6比2大,所以不用交换1 5 3 2 6
2和3比较,2小,所以2和3交换 1 5 2 3 6
2和5比较,2小,所以2和5交换 1 2 5 3 6
2和1比较,2大,所以不用交换,此时这一趟遍历不仅将最小值放到了第一的位置,而且12,25,23之间也是有序的了
void BubbleSort2(SqList *L)
{
int i,j;
for(i=1;i<=L->length;i++)
{
for(j=L->length-1;j>=i;j--) //相邻比较,从后往前冒泡,直到第一个泡一定是最小的
{
if(L->r[j+1]<L->r[j])
{
swap(L,j+1,j);
}
}
}
}
冒泡排序3.0(冒泡排序的优化)
冒泡排序2.0在待排序的数组已经有序的情况下,比如1,5,3,2,6在第二轮1 2 3 5 6就已经有序了,但是由于此时的i=2,还要进行i=3,i=4,i=5的情况下的没有必要的近邻比较,所以如果在i=3走完一轮后,若发现没有交换数字,即为已经有序,就停止循环好了
void BubbleSort3(SqList *L)
{
int i=0,j;
bool flag = true;
for(i=1;i<=L->length&&flag;i++)
{
printf("\n%d",i);//打印i的值,查看循环了几次
flag=false;
for(j=L->length-1;j>=1;j--)
{
if(L->r[j+1]<L->r[j])
{
swap(L,j,j+1);
flag=true;
}
}
}
}
从i值的打印情况可见,在第三轮的时候发现没有交换就结束遍历了
测试程序:
int main()
{
SqList L;
CreateSq(L);
//BubbleSort1(&L);
//BubbleSort2(&L);
BubbleSort3(&L);
PrintSq(L);
}
冒泡排序复杂度分析:
最好的情况是已经有序的顺序表,需要有n-1此比较,0此交换,复杂度为O(n)
最坏的情况是逆序的情况,需要有1+2+3+...n-1此比较和移动,复杂度为O(n^2)
上一篇: springmvc支持跨域的请求(复制)
下一篇: Mybatis—⑤使用注解开发