简单冒泡排序的时间复杂度及其两种优化_电气自动化网
首页 资讯 应用 高压 设计 行业 低压 电路图 关于

单片机

旗下栏目: PLC 嵌入式 单片机 DCS

简单冒泡排序的时间复杂度及其两种优化

单片机 | 发布时间:2018-06-01 | 人气: | #评论# | 本文关键字:C,C语言,冒泡排序
摘要:在我们写一些简单的程序中,对一组数据进行简单的有序的排列是经常会遇到的,所以我们必须熟悉几种基本的算法。 而冒泡排序就是我们学习排序的基础, 冒泡排序: 形象的可以理解为:

在我们写一些简单的程序中,对一组数据进行简单的有序的排列是经常会遇到的,所以我们必须熟悉几种基本的算法。而冒泡排序就是我们学习排序的基础,冒泡排序:形象的可以理解为:水中上升的气泡,在上升的过程中,气泡越来越小,不断比较相邻的元素,将小的往后调

我们来解决这样一个问题:设有一数组,其大小为6个元素(int array[6]),数组内的数据是(4,2,5,3,2,6),此刻数据是无序的,现要求我们编程将其变成一个有序的从大到小的数组,从下标0开始。

思考:按照题目要求,毫无疑问,最终的有序数组应该是这样(6,5,4,3,2,2),要做到这样,最简单的办法就是进行比较交换

1:我们从数组的第一个元素array[0]向后走,如果比相邻的小,那么交换,如此进行下去,可以发现,我们找到了所

      有元素中最小的并且已经将它放在了最后一个位置array[5]

2:然后,我们重新从第一个元素向后走,还是相邻的比较,并且交换,但是我们只需要比较到4,放在array[4]

3:重复第二步,直到比较到1

代码:

  1. #include <stdio.h>  

  2. #include <iostream>  

  3. using namespace std;  

  4. void Bubble_sort(int *array, int length)  

  5. {  

  6.         //变量i,j用于循环,变量t用于交换中间值  

  7.         int i, j, t;  

  8.         for(i = 1; i < length; i++)  

  9.         {         

  10.                 //比较的次数越来越少,但是每一个都能在相应的范围内确定一个最小值并放在合理的位置  

  11.                 for(j = 0; j < length - i ; j++)  

  12.                 {  

  13.                         //在满足条件的情况下,交换两个数  

  14.                         if(array[j] < array[j + 1])  

  15.                         {  

  16.                                 t = array[j];  

  17.                                 array[j] = array[j + 1];  

  18.                                 array[j + 1] = t;  

  19.                         }  

  20.                 }  

  21.         }  

  22.         //将6个数输出  

  23.         for(i = 0; i< length; i++)  

  24.                 cout<<array[i]<<endl;  

  25. }  

  26. int main()  

  27. {  

  28.         int array[] = {4,2,5,3,2,6};        //定义一个数组并简单的初始化  

  29.         int length = sizeof(array)/sizeof(int);//求定义数组的具体长度  

  30.         Bubble_sort(array, length);     //调用相应的排序函数  

  31.           

  32.         return 0;         

  33. }  

关于优化:我们必须从时间复杂度和空间复杂度上面来看

好多人一直都在纠结冒泡排序的时间复杂度

在最坏的情况下是:O(N)

还是在最坏的情况下是比较比较次数是:n(n - 1)/ 2

他们两到底是什么关系???

其实:总而言之,冒泡排序是一种用时间在换空间的排序。

最坏的情况当然是:每一次的比较都会进行交换,也就是说要把逆序的数列变成顺序或者要把顺序变成逆序,5,4,3,2,1以冒泡升序排列

1,从第一个数5开始和后面的数进行比较比较到倒数第二个数2为止,过程为:5跟4比较,5比4大,两者交换,然后 跟3比较,5比3大,继续进行交换,依次进行比较,比较完成为:4,3,2,1,5

2,从第一个数4开始和后面的数进行比较,过程为:4跟3比较,4比3大,两者进行交换,然后跟2进行比较,4比2大 ,继续交换,依次比较,比较完成为:3,2,1,4,5

3,同理所以总的比较次数就是:4 + 3 + 2 + 1,所以,对于n位数的比较次数就是:n + (n - 1)+(n -2)+...+1 = n(n - 1)/ 2

而O(N^2)表示的是复杂度的数量级,举个例子来说,如果n = 10000,那么n(n -1 )/2 = (n^2 - n)/ 2

= (100000000 - 10000)/2,相对于10^8来说,10000可以忽略不计,所以总计算次数约为0.5 * N^2.

所以,就用O(N^2)表示了数量级(忽略了前面的系数0.5)

所以,我们可以从趟数上面处理,因为有可能我们比较一定的倘数之后就已经变成了有序的了,没有必要再去做一些无用的比较了

如:5,1,2,3,4

冒泡一次之后就变成了:1,2,3,4,5已经有序了,我们没有必要再去比较了

程序:

  1. #include <stdio.h>  

  2. #include <iostream>  

  3. using namespace std;  

  4. void Bubble_sort(int *array, int length)  

  5. {  

  6.         int i, j, t;  

  7.         int flag;                    //标志量,用于指示,数列已然是有序的  

  8.         for(i = 1; i < length; i++)  

  9.         {         

  10.                 flag = 1;  

  11.                 for(j = 0; j < length - i ; j++)  

  12.                 {  

  13.                         if(array[j] < array[j + 1])   //合理的交换相邻的两个数  

  14.                         {  

  15.                                 flag = 0;  

  16.                                 t = array[j];  

  17.                                 array[j] = array[j + 1];  

  18.                                 array[j + 1] = t;  

  19.                         }  

  20.                 }  

  21.                 if(flag == 1)         //标志位  

  22.                         break;  

  23.         }  

  24.           

  25.         for(i = 0; i< length; i++)//输出排序后的数列  

  26.                 cout<<array[i]<<endl;  

  27. }  

  28.   

  29. int main()  

  30. {  

  31.         int array[] = {4,2,5,3,2,6};  

  32.         int length = sizeof(array)/sizeof(int);  

  33.         Bubble_sort(array, length);  

  34.           

  35.         return 0;         

  36. }  

这里我们加入了标志,flag,如果有一趟排序中没有产生交换的话,那么说明此刻数列以及变成了有序的数列

责任编辑:冒泡排序
首页 | 电气资讯 | 应用技术 | 高压电器 | 电气设计 | 行业应用 | 低压电器 | 电路图 | 关于我们 | 版权声明

Copyright 2017-2018 电气自动化网 版权所有 辽ICP备17010593号-1

电脑版 | 移动版 原创声明:本站大部分内容为原创,转载请注明电气自动化网转载;部分内容来源网络,如侵犯您的权益请发送邮件到[email protected]联系我们删除。