基础算法之冒泡排序（bubble sort）

短命女 2022-05-29 05:05 270阅读 0赞

**0，（注）**

由于冒泡排序也分为升序（**asc**）和降序（**desc**）排列，为了防止过多的代码，因此我们次文只选择**升序**作为展示，完整的优化降序代码也将会在文章尾部（**Example1**）贴出来。那么接下来我们一起来进入可爱的冒泡算法吧！

**1，算法名称：**升序冒泡排序（ascending bubble sort）

**2，时间复杂度：**O（n^2）

**3，实现方式：**C语言

**4，空间复杂度：**O（1）

**5，稳定性：**稳定

**6，算法思想：**

.比较相邻的元素。如果第一个比第二个大，就交换它们两个；

.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；

.针对所有的元素重复以上的步骤，除了最后一个；

.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

**7，算法实现**

在实现算法中，我们会首先从最简单的一板开始，然后分析其中的不足，最后在贴出它的优化后的算法。

7.1  基础版的算法代码

#include<stdio.h>  
    #include<stdlib.h>
    /* 交换函数 */
    swap(int *a,int *b){
    	int temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    } 
      
    /* 升序冒泡 */
    void bubblesortAsc(int *a,int len)  
    {  
    	int i,j;
    	for(i = 0; i < len-1; i++){
    		/*每排序一趟，则至少有一个元素已经有序,用 j<len-i-1 可以缩小排序范围 */  
    		for(j = 0; j < len-1-i;j++){
    			if(a[j] > a[j+1]){
    				swap(&a[j],&a[j+1]);
    			}
    		}
    	}
    }  
    int main()  
    {  
    	int num[5]={3,1,5,6,2};  
    	int i=0;  
    	bubblesortAsc(num,5);  
    	for(i=0;i<5;i++)  
    	{  
    		printf("%d ",num[i]);  
    	}	  
    	return 0;  
    }

存在问题：可以看出，整体的排序过程比较繁琐，主要是因为要进行两次的循环，并且循环的次数全为N，有一种情况，那就是未排序的序列如果已经是有序排列了，那么算法就要执行好多多余的步骤，就上边的代码实现，假如现在：

int num[5] = {6,1,2,3,5};

我们可以直观的观察出，此代码只要执行一次外部循环就可以成为有序序列，但是由于我们没有及时的中断它的操作，因此造成了许多不必要的比较。

优化方法：对函数加一个flag标识，假如一次的循环中没有发生swap(),那么我们就比较flag的值，执行跳出函数操作！具体情况参见代码。

7.2  优化版的算法代码

#include<stdio.h>  
    #include<stdlib.h>
    /* 交换函数 */
    swap(int *a,int *b){
    	int temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    } 
      
    /* 升序冒泡 */
    void bubblesortAsc(int *a,int len)  
    {  
    	int i,j;
    	bool flag;	//没有交换的标记 
    	for(i = 0; i < len-1; i++){
    		flag = 0; 
    		/*每排序一趟，则至少有一个元素已经有序,用 j<len-i-1 可以缩小排序范围 */  
    		for(j = 0; j < len-1-i;j++){
    			if(a[j] > a[j+1]){
    				swap(&a[j],&a[j+1]);
    				flag = 1; 
    			}
    		}
    		if(!flag) break;
    	}
    }  
    int main()  
    {  
    	int num[5]={3,1,5,6,2};  
    	int i=0;  
    	bubblesortAsc(num,5);  
    	for(i=0;i<5;i++)  
    	{  
    		printf("%d ",num[i]);  
    	}	  
    	return 0;  
    }

**---------------------------END\--------------------------------**

**Example 1**

#include<stdio.h>  
    #include<stdlib.h>
    /* 交换函数 */
    swap(int *a,int *b){
    	int temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    } 
      
    /* 降序冒泡 */
    void bubblesortAsc(int *a,int len)  
    {  
    	int i,j;
    	bool flag;	//没有交换的标记 
    	for(i = 0; i < len-1; i++){
    		flag = 0; 
    		/*每排序一趟，则至少有一个元素已经有序,用 j<len-i-1 可以缩小排序范围 */  
    		for(j = 0; j < len-1-i;j++){
    			if(a[j] < a[j+1]){
    				swap(&a[j],&a[j+1]);
    				flag = 1; 
    			}
    		}
    		if(!flag) break;
    	}
    }  
    int main()  
    {  
    	int num[5]={3,1,5,6,2};  
    	int i=0;  
    	bubblesortAsc(num,5);  
    	for(i=0;i<5;i++)  
    	{  
    		printf("%d ",num[i]);  
    	}	  
    	return 0;  
    }

其实就是把其中的“>”"<"号发生了更改。

**参考：[冒泡排序算法及其优化  
][Link 1]**

**[         基础算法总结][Link 2]**

[Link 1]: http://blog.csdn.net/llzk_/article/details/51547923
[Link 2]: http://blog.csdn.net/zzzzlei123123123/article/details/79592504