97-对冒泡排序算法的实现和分析

落日映苍穹つ 2022-12-29 00:07 133阅读 0赞

***冒泡排序算法的思想***

1.比较两个相邻的数据，将较大的数据往后交换，将最大的数据交换到数据序列的最后  
2.循环以上过程，每次都会少一个最大数据

***冒泡排序算法的分析***

时间复杂度： O(n^2)  
空间复杂度：O(1)----> 主要考虑malloc的空间与n有没有关系，递归次数与n有没有关系  
稳定性： 稳定

首先，先书写出需要用到的辅助函数

#include<stdio.h>
    
    /*辅助函数：
        1.打印数据
    	2.判断整个数据序列是否已经有序
    	3.交互两个数据swap方法
    */
    
    void Show(int *arr,int len)//打印数据
    {
        
    	for(int i=0;i<len;++i)
    	{
        
    		printf("%d  ",arr[i]);
    	}
    	printf("\n");
    }
    
    bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
    {
        
    	for(int i=0;i<len-1;++i)
    	{
        
    		if(arr[i]>arr[i+1])
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    
    void SwapValue(int *a,int *b)//交互两个数据swap方法
    {
        
    	int tmp=*a;
    	*a=*b;
    	*b=tmp; 
    }

下面是冒泡排序的过程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
接下来书写冒泡排序函数

void BubbleSort1(int *arr,int len)
    {
        
    	for(int j=0;j<len-1;++j)//趟数 
    	{
        
    		for(int i=0;i<len-1-j;++i)
    		{
        
    			if(arr[i]>arr[i+1])
    			{
        
    				SwapValue(&arr[i],&arr[i+1]);
    			}
    		}
    	} 
    }

最后书写主函数

int main()
    {
        
    	int arr[]={
        7,87,29,75,41,50,62,92,69,22,76,77,35};
    	Show(arr,sizeof(arr)/sizeof(arr[0]));
    	BubbleSort1(arr,sizeof(arr)/sizeof(arr[0]));
    	Show(arr,sizeof(arr)/sizeof(arr[0])); 
    	return 0;
    	
    }

运行截图如下  
![在这里插入图片描述][20201218105701762.png_pic_center]  
最后，对这个冒泡排序算法函数进行简单优化一下  
对时间复杂度没有任何影响  
针对一些情况进行优化，对比较有序的数组，可以省去一些遍历比较过程

void BubbleSort2(int *arr,int len)
    {
        
    	for(int j=0;j<len-1;++j)//趟数 
    	{
        
    		bool flag=false; 
    		for(int i=0;i<len-1-j;++i)
    		{
        
    			if(arr[i]>arr[i+1])
    			{
        
    				SwapValue(&arr[i],&arr[i+1]);
    				flag=true;
    			}
    		}
    		if(!flag)
    		{
        
    			break;
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/bd2110971da14125896b9546b543dced.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/98c37c16b7364bd3afb4d6a280a15cb0.png
[20201218105701762.png_pic_center]: /images/20221120/38a8f304676f4ad89ca0f281692ba9e1.png