数据结构 — 冒泡排序以及其优化

以你之姓@ 2022-06-05 06:38 187阅读 0赞

# 冒泡排序 #

我以前一直对冒牌排序不以为然，作为最容易写出来的排序.直到前两天我被人问到一个问题，让我把普通的冒泡排序最好的时间复杂度

优化到O(N). 当然冒泡排序最坏时间复杂度O(N^2)这个没有办法改变.我们只能尽量优化它的过程让它少走几次循环. 其实仔细做起来，我

在写程序有时候还是太片 面了 不能够考虑到最优的效率，只是单纯的实现功能，这样不好. 好了进入正题，我们首先了解冒泡排序的过

程 和原理. 所谓的冒泡排序将被排序的记录数组A\[1...N\] 垂直排列，每一个记录A\[i\]看作重量为R\[i\].key的气泡.根据轻气泡不能在重气

泡 之下的原则,从下往上 扫 描数组A.凡扫描到违反本原则的轻气泡，就让他往上漂浮, 如此反复进行。知道最后任何两个气泡都是轻者在上

，重者在下为止为止,我这里使用一 张图 帮我们理解. 该图为冒牌排序的过程.

![20171120151443330][]

动态过程:

![20171120152609024][]

这个排序的基本代码非常容易实现如下所示:

void popsort(int* a, size_t n)
    {
    	int i = 0;
    	int j = 0;;
    	int tmp = 0;
    
    	for (i  = 0; i < n - 1; i++)
    	{
    		for (j = 0; j < n - i - 1; j++)
    		{
    			if (a[j] > a[j + 1])
    			{
    				tmp = a[j];
    				a[j] = a[j + 1];
    				a[j + 1] = tmp;
    			}
    		}
    	}
    }

它的时间复杂度非常容易理解:O(N^2). 但是我们仔细看看上面的图.从第六次循环的时候整个数组其实已经排好序了，后面的循环其实

都是多余的操作 我们程序员是一个追求效率的东西，所以呢我们要想办法解决掉这个问题, 这个时候我有这么一个想法，我们可不可

以这么想. 如果我循环一趟没有发 生交换，那么这个数组整个就排好序了.这里认真想，如果你一趟下来下来没有交换任何数据，说明你

这个数组的每一个位置a\[i\]<a\[i+1\]，那么它肯定 有序啊.所以我们可以使用一个标记变量，然后如果交换了就改变标记变量的值.如果内

循环一趟出来，标记变量没有变化那就是排好序了.代码实现:

//外循环优化->
    void popsort1(int* a, size_t n)
    {
    	int i = 0;
    	int j = 0;;
    	int tmp = 0;
    	int Pos = 1;
    
    	for (i = 0; i < n - 1; i++)
    	{
    		if (Pos == 0)
    			break;
    
    		Pos = 0;
    
    		for (j = 0; j < n - i - 1; j++)
    		{
    			if (a[j] > a[j + 1])
    			{
    				Pos = 1;
    				tmp = a[j];
    				a[j] = a[j + 1];
    				a[j + 1] = tmp;
    			}
    		}
    	}
    }

运行结果:

![20171120152446080][]

运行结果我们看到了程序减少了循环次数，节约了效率,现在程序最好的时间复杂度为O(N). 就是刚刚好数组有序的时候.最坏的时间

复杂度还是O(N^2) 现在我们思考还可不可以优 化？？ 让它的平均时间复杂度能够更好一点. 现在我们只能从内部这个

for (j = 0; j < n - i - 1; j++)循环入手了. 我们想让她少循环一点，只能从j < n-i-1这里入手.这里我还有一种思路，我们首先

明白一个原理,设每次最后交换的地方为k. 那么a\[k\]~a\[N\]一定是 有序的.如果你好好思考一下，看看这个道理到底对不对. 想不来

没关系，我还有图！！！

![20171120153936780][]

那么优化就很简单了，只需要改变内层for循环判断条件. 每次记录最后一次交换数据的位置K，然后for (j = 0; j < K; j++)这样

改变for循环条件即 可.这样我们的优化就完毕了~ 这个时候你的冒泡排序法的效率将会大大提高.你已经很尽力的优化它了. 由于

这个优化效果没有办法直观展示.直接 代码实现了:

//内循环优化->
    void popsort3(int* a, size_t n)
    {
    	int i = 0;
    	int j = 0;;
    	int tmp = 0;
    	int Pos = 1;
    	int K = n-1;
    	int M = 0;
    
    	for (i = 0; i < n - 1; i++)
    	{
    		if (Pos == 0)
    			break;
    
    		Pos = 0;
    
    		for (j = 0; j < K; j++)
    		{
    			if (a[j] > a[j + 1])
    			{
    				Pos = 1;
    				tmp = a[j];
    				a[j] = a[j + 1];
    				a[j + 1] = tmp;
    				M = j;
    			}
    		}
    		K = M;
    	}
    }

冒泡排序这个算法大概优化就这么多吧. 我们平时写代码记着多多想着代码可不可以优化.这才是一个好的程序员的标准. 排序

这里 还有很多方法, 比如和冒泡很相似的 [插入排序][Link 1] . 如果不了解可以戳进来.

[20171120151443330]: /images/20220605/6365a23169a04db6a332b146398f0628.png
[20171120152609024]: /images/20220605/eeb47203117549ee8b083c4c950f1dcb.png
[20171120152446080]: /images/20220605/7a508f5fd93f45ada3fa4b9ff62f3304.png
[20171120153936780]: /images/20220605/1a57ab8d68bd4dabaebdc308a795025b.png
[Link 1]: http://blog.csdn.net/dawn_sf/article/details/77692857