赞
踩
1.算法的基本思想
冒泡排序是交换排序的一种,我们可以把将待排序的数组Arrray[0...n-1]理解成一个圆柱,将数组中的每一个元素都看成是重量为Array[i]的气泡,其中Array[0]在最上面 ,Array[n]在最下面。排序时候根据轻气泡在上重气泡在下的原则,自上而下扫描数组Array,遇到违反原则的气泡,就使其向下“下沉”,知道所有的气泡都是轻气泡在上重气泡在下,算法结束。
2.算法流程
1)初始时Array[0...n-1]无序,对n个元素序列进行n-1趟扫描。
2)第一趟扫描,自上而下比较数组R相邻的两个气泡的重量。若发现轻者在下、重在上,则交换两个气泡位置。
3)第二趟扫描,“次重”的气泡就被送到Array[n-2]的位置上。
4)按照如上方法进行扫描,每趟的扫描次数都比上次少一次。直到进行n-1趟扫描,算法结束。
3.算法实现
下面给出冒泡排序算法的实现代码
- /*
- 函数功能:对无序序列进行基本的冒泡排序
- 函数参数:参数1,待排序的数组;参数2,待排序数组大小
- */
- void BubbleSort(int *Array,int n)
- {
- int temp,i,j;
- for(i=n-1;i<0;i++)
- for(j=0;j<i;j++)
- if(*(Array+j)>*(Array+j+1))
- {
- temp=*(Array+j);
- *(Array+j)=*(Array+j+1);
- *(Array+j+1)=temp;
- }
- }
- /*主程序*/
- void main()
- {
- int Array[8]={5,7,9,2,3,11,4};
- int i;
- printf("待排序数组为:\n");
- for(i=0;i<8;i++)
- pringf("%d ",*(Array+i));
- BubbleSort(Array,8);
- printf("\n冒泡排序后的数组为:\n");
- for(i=0;i<8;i++)
- printf("%d ",*(Array+i));
- }
4.冒泡排序的改进算法
通过对简单冒牌排序算法的分析,我们不难得出这样一个结论:每一趟比较结束后,若发现从某一个位置r开始,不再记录交换,就说明从Array[r+1]到Array[n-1]已经排序好了,从而下一趟比较只要进行到位置r就可以了。若某一趟扫描中没有记录交换,则说明所有元素都已有序,算法可以结束了,而不是必须进行n-1趟扫描。基于这种思想,可以给出一种冒泡排序的改进算法。
冒泡排序改进算法1,主要是记录了最后一次发生交换发生的位置
- /*
- 函数功能:对无序序列进行基本的冒泡排序
- 函数参数:参数1,待排序的数组;参数2,待排序数组大小
- */
- #include<stdio.h>
-
- void BubbleSort(int* Array, int n)
- {
- int bound = n;
- int i, m;
- int temp;
- while (bound != 0)
- {
- for (i = 0;i < bound;i++)
- {
- if (*(Array + i) > *(Array + i + 1))
- {
- temp = *(Array + i);
- *(Array + i) = *(Array + i + 1);
- *(Array + i + 1) = temp;
- m = i;/*用m来记录最后一次发生交换的位置*/
- }
- }
- bound = m;
- }
- }
- /*主程序*/
- int main()
- {
- int Array[8] = { 5,7,9,2,3,11,4 };
- int i;
- printf("待排序数组为:\n");
- for (i = 0;i < 8;i++)
- printf("%d ", *(Array + i));
- BubbleSort(Array, 8);
- printf("\n冒泡排序后的数组为:\n");
- for (i = 0;i < 8;i++)
- {
- printf("%d ", *(Array + i));
- }
- }
冒泡排序改进算法2(双向起泡),该算法中下沉和上浮是交替的。
- /*
- 函数功能:对无序序列进行基本的冒泡排序
- 函数参数:参数1,待排序的数组;参数2,待排序数组大小
- */
- #include<stdio.h>
-
- void BubbleSort(int* Array, int n)
- {
- int boundmin = 0;
- int boundmax = n;
- int mmin,mmax,i;
- int temp;
- while (boundmin<boundmax)
- {
- mmin = 0;
- mmax = 0;
- for (i = boundmin;i < boundmax;i++)/*此次扫描使重气泡下沉*/
- {
- if (*(Array + i) > *(Array + i + 1))
- {
- temp = *(Array + i);
- *(Array + i) = *(Array + i + 1);
- *(Array + i + 1) = temp;
- mmax = i;/*用mmax来记录下沉最后一次发生交换的位置*/
- }
- }
- if (mmax == 0)/*本次扫描没有记录交换,扫描结束*/
- break;
- boundmax = mmax;
- for (i = boundmax-1;i < boundmin;i--)/*此次扫描使轻气泡上浮*/
- {
- if (*(Array + i) <*(Array + i - 1))
- {
- temp = *(Array + i);
- *(Array + i) = *(Array + i - 1);
- *(Array + i -1) = temp;
- mmin= i;/*用mmin来记录上升最后一次发生交换的位置*/
- }
- }
- if (mmin == 0)/*本次扫描没有记录交换,扫描结束*/
- break;
- boundmin = mmin;
- }
- }
- /*主程序*/
- int main()
- {
- int Array[8] = { 5,7,9,2,3,11,4,8 };
- int i;
- printf("待排序数组为:\n");
- for (i = 0;i < 8;i++)
- printf("%d ", *(Array + i));
- BubbleSort(Array, 8);
- printf("\n冒泡排序后的数组为:\n");
- for (i = 0;i < 8;i++)
- {
- printf("%d ", *(Array + i));
- }
- }
5.性能评价
时间复杂度:最好为O(n),最坏为O(n2),因此平均时间复杂度为O(n2)。
空间复杂度:冒泡排序是就地排序,空间复杂度为O(1)。
稳定性:由算法流程知,冒牌排序是稳定的。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。