冒泡排序及其优化

深碍√TFBOYSˉ_ 2024-04-18 19:51 3阅读 0赞

我偶然看了一篇写的比较好冒泡排序优化的博客，自己整理了一下，分享给大家，一起学习。若有错误，欢迎大家指正~

**冒泡排序(BubbleSort)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2MDc5MDkz_size_16_color_FFFFFF_t_70]  
图片来自：https://blog.csdn.net/u013457167/article/details/81989207

**复杂度和稳定性情况：**  
最好的时间复杂度：O（n）  
最坏的时间复杂度：O（n²）  
平均的时间复杂度：O（n²）  
空间复杂度：O（1）  
稳定性：稳定

**一般冒泡排序写法**

#include<iostream>
    using namespace std;
    
    void BubbleSort(int arr[],int len) //冒泡排序函数，arr[]做参数退化为一个指针，接受数组的首地址
    {
    	int temp;
    	for(int i = 0; i < len - 1; ++i) //排序的次数
    	{
    		for(int j = 0; j < len -i-1; ++j) //每次排序的比较次数
    		{
    			if(arr[j] > arr[j+1]) //比较大小，大的往后放
    			{
    				temp = arr[j];
    				arr[j] = arr[j+1];
    				arr[j+1] = temp;
    			}
    		}
    	}
    	for(int k = 0; k < len; ++k) //打印排序好的数组，用于测试
    	{
    		cout<<arr[k]<<" ";
    	}
    	cout<<endl;
    }
    
    void main()
    {
    	int a[] = {1,3,4,2,6,7,8,0};
    	int length = sizeof(a) / sizeof(int); //计算数组的长度
    	BubbleSort(a,length); //调用冒泡排序函数，a传入数组的首地址
    }

**优化一**  
假设我们现在排序ar\[\]=\{1,2,3,4,5,6,7,8,10,9\}这组数据，按照上面的排序方式，第一趟排序后将10和9交换已经有序，接下来的8趟排序就是多余的，什么也没做。所以我们可以在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。

优化一冒泡排序的代码如下：

#include<iostream>
    using namespace std;
    
    void BubbleSort(int arr[],int len)  //冒泡排序优化一函数，arr[]做参数退化为一个指针，接受数组的首地址
    {
    	int temp;
    	int flag = 0; //设置一个标记
    	for(int i = 0; i < len-1; ++i)  	//排序的次数
    	{
    		flag = 0;
    		for(int j = 0; j < len-i-1; ++j)  //每次排序的比较次数
    		{
    			if(arr[j] > arr[j+1])  //比较大小，大的往后放
    			{
    				temp = arr[j];
    				arr[j] = arr[j+1];
    				arr[j+1] = temp;
    				flag = 1; //本次排序有变动，将标记设为1
    			}
    		}
    		if(flag == 0) //若标记flag未变化，说明数组排序完成，直接返回
    		{
    			return;
    		}	
    	}
    	for(int k = 0; k < len; ++k)   //打印排序好的数组，用于测试
    	{
    		cout<<arr[k]<<" ";
    	}
    	cout<<endl;
    }
    
    void main()
    {
    	int a[8] = {1,3,4,2,6,7,8,0};
    	int length = sizeof(a) / sizeof(int); //计算数组的长度
    	BubbleSort(a,length);   //调用冒泡排序函数，a传入数组的首地址
    }

**优化二**  
优化一仅仅适用于连片有序而整体无序的数据(例如：1， 2，3 ，4 ，7，6，5)。但是对于前面大部分是无序而后边小半部分有序的数据(1，2，5，7，4，3，6，8，9，10)排序效率也不可观，对于种类型数据，我们可以继续优化。既我们可以记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2MDc5MDkz_size_16_color_FFFFFF_t_70 1]

优化二冒泡排序的代码如下：

#include<iostream>
    using namespace std;
    
    void BubbleSort(int arr[],int len)  //冒泡排序优化二函数，arr[]做参数退化为一个指针，接受数组的首地址
    {
    	int temp = 0;
    	int flag = 0;  //设置一个标记
    	int pos = 0;  //用来记录最后一次交换的位置
    	int k = len-1;
    	for(int i = 0; i < len-1; ++i)  //排序的次数
    	{
    		flag = 0;
    		pos = 0;
    		for(int j = 0; j < k; ++j)   //每次排序的比较次数
    		{
    			if(arr[j] > arr[j+1]) //比较大小，大的往后放
    			{
    				temp = arr[j];
    				arr[j] = arr[j+1];
    				arr[j+1] = temp;
    				flag = 1; //本次排序有变动，将标记设为1
    				pos = j;  //记录本次排序最后一次交换的位置
    			}
    		}
    		if(flag == 0)  //若标记flag未变化，说明数组排序完成，直接返回
    		{
    			return;
    		}
    		k = pos; //将最后一次交换的位置传给k，减少不必要的循环次数
    	}
    	for(int x = 0; x < len; ++x)  //打印排序好的数组，用于测试
    	{
    		cout<<arr[x]<<" ";
    	}
    	cout<<endl;
    }
    
    void main()
    {
    	int a[] = {1,3,4,2,6,7,8,0};
    	int length = sizeof(a) / sizeof(int); //计算数组的长度
    	BubbleSort(a,length);   //调用冒泡排序函数，a传入数组的首地址
    }

**优化三**  
优化二的效率有很大的提升，还有一种优化方法可以继续提高效率。大致思想就是一次排序可以确定两个值，正向扫描找到最大值交换到最后，反向扫描找到最小值交换到最前面。例如：排序数据1，2，3，4，5，6，0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2MDc5MDkz_size_16_color_FFFFFF_t_70 2]  
优化三的冒泡排序代码如下：

#include<iostream>
    using namespace std;
    
    //冒泡改进版
    void BubbleSort(int arr[],int len)  //冒泡排序优化三函数，arr[]做参数退化为一个指针，接受数组的首地址
    {
    	int temp;
    	int flag;  //设置一个标记
    	int pos;  //用来记录最后一次交换的位置
    	int left = 0;    //表示范围
            int right = len-1;
    	for(int i = 0; i < len-1; ++i)  //排序的次数
    	{
    		flag = 0;
    		pos = 0;
    		//正向寻找最大值
    		for(int j = left; j < right; ++j)   //每次排序的比较次数
    		{
    			if(arr[j] > arr[j+1]) //比较大小，大的往后放
    			{
    				temp = arr[j];
    				arr[j] = arr[j+1];
    				arr[j+1] = temp;
    				flag = 1; //本次排序有变动，将标记设为1
                                    pos = j;
    			}
    		}
    		if(flag == 0)  //若标记flag未变化，说明数组排序完成，直接返回
    		{
    			return;
    		}
    		right = pos; //将right往中间靠拢
    		flag = 0;
    		for(j = right; j > left; --j)
    		{
    			if(arr[j] < arr[j-1])  //比较大小，小的往前放
    			{
    				temp = arr[j-1];
    				arr[j-1] = arr[j];
    				arr[j] = temp;
    				flag = 1; //本次排序有变动，将标记设为1
                                    pos = j;
    			}
    		}
    		if(flag == 0)   //若标记flag未变化，说明数组排序完成，直接返回
    		{
    			return;
    		}
    		left = pos; //左右扫描范围缩小，往中间靠拢
    	}
    }
    
    void main()
    {
    	int a[] = {2,1,3,6,5,4,0};
    	int len = sizeof(a) / sizeof(int); //计算数组的长度
    	BubbleSort(a,len);   //调用冒泡排序函数，a传入数组的首地址
            for(int x = 0; x < len; ++x)  //打印排序好的数组，用于测试
    	{
    	    cout<<a[x]<<" ";
    	}
    	cout<<endl;
    }

其他排序算法：

1、 [堆排][Link 1]  
2、 [直接插入排序][Link 2]  
3、 [希尔排序（优化版）][Link 3]  
4、[直接选择排序][Link 4]  
5、[快速排序(递归版和非递归版)][Link 5]  
6、[归并排序][Link 6]  
7、[基数排序][Link 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2MDc5MDkz_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/467fc74560be4a08ad016ecbd49e2094.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2MDc5MDkz_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a1bbe582a4cc4bbd83b1978228581567.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2MDc5MDkz_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ca81281eb2354ab59ca1ee16bf14b42d.png
[Link 1]: https://blog.csdn.net/qq_26079093/article/details/94774112
[Link 2]: https://blog.csdn.net/qq_26079093/article/details/96187844
[Link 3]: https://blog.csdn.net/qq_26079093/article/details/96271978
[Link 4]: https://blog.csdn.net/qq_26079093/article/details/96310781
[Link 5]: https://blog.csdn.net/qq_26079093/article/details/96319089
[Link 6]: https://blog.csdn.net/qq_26079093/article/details/97612703
[Link 7]: https://blog.csdn.net/qq_26079093/article/details/97614526