冒泡排序算法以及优化

约定不等于承诺〃 2022-12-25 12:53 14阅读 0赞

什么是冒泡排序呢？冒泡排序的英语名是Bubble Sort，是一种最基础的交换排序。

大家一定都喝过汽水吧，汽水中常常有许多小小的气泡，往上飘，这是因为组成小气泡的二氧化碳比水要轻，所以小气泡才会一点一点的向上浮。而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以向小气泡一样，根据自身大小，一点一点向着数组的一侧移动。具体如何移动呢？我们来看一下例子：

![img][]

有8个数组组成一个无序数列：5,8,6,3,9,2,1,7，希望从大到小排序。按照冒泡排序的思想，我们要把相邻的元素两两进行比较，根据大小交换元素的位置，过程如下：

**第一轮排序：**

1、首先让5和8进行交换，发现5比8小，因此元素位置不变。

2、接下来让8和6比较，发现8比6大，所以要交换8和6的位置。3、

![img][img 1]

3、继续让8和3比较，发现8比3要大，所以8和3 交换位置。

![img][img 2]

4、继续让8和9进行比较，发现8比9小，不用交换

5、9和2进行比较，发现9比2大，进行交换

![img][img 3]

6、继续让9和1进行比较，发现9比1大，所以交换9和1的位置。

![img][img 4]

7、最后，让9和7交换位置

![img][img 5]

这样一来，元素9作为数列的最大元素，就已经排序好了。

![img][img 6]

**下面我们来进行第二轮排序：**

1、首先让5和6比较，发现5比6小，位置不变

2、接下来让6和3比较，发现6比3大，交换位置

![img][img 7]

3、接下来让6和8比较，6比8小，位置不变

4、8和2比较。8比2大，交换位置

![img][img 8]

5、接下来让8和1比较，8比1大，因此交换位置

![img][img 9]

6、继续让8和7比较，发现8比7大，交换位置

![img][img 10]

第二轮的状态为：

![img][img 11]

第三轮的状态为：

![img][img 12]

第四轮的状态为：

![img][img 13]

第五轮的状态为：

![img][img 14]

第六轮的状态：

![img][img 15]

第七轮状态为：（已经有序了）

![img][img 16]

第八轮的状态为：

![img][img 17]

到此为止，所有的元素欧式有序的了，这就是冒泡排序的整体思路。

原始的冒泡排序是稳定的，由于该排序算法的每一轮都要遍历一遍所有的元素，轮转的次数和元素数量相当，所以时间复杂度为O(N^2)。

方法一：

#include<stdio.h>
    #include<stdlib.h>
     
    void BubbleSort(int a[], int len)
    { 
    	int i, j, temp;
    	for (j = 0; j < len - 1; j++)
    	{ 
    		for (i = 0; i < len - 1 - j; i++)
    		if (a[i] > a[i + 1])
    		{ 
    			temp = a[i];
    			a[i] = a[i + 1];
    			a[i + 1] = temp;
    		}
    	}
    }
     
    int main()
    { 
    	int arr[] = {  5, 8, 6, 3, 9, 2, 1, 7 };
    	int len = sizeof(arr) / sizeof(arr[0]);
    	int i = 0;
    	printf("排序前：");
    	for (i = 0; i < len; i++)
    	{ 
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
     
    	BubbleSort(arr, len);
    	printf("排序后：");
    	for (i = 0; i < len; i++)
    	{ 
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }

这个代码很简单，使用双循环的方式进行排序。外部的循环控制所有回合，内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换。\*\*那么这个代码该怎么进行优化呢？？\*\*我们现在来回顾一下之前的描述细节，仍然以 5,8,6,3,9,2,1,7 为例，当排序伏安法分别执行到第六、第七、第八轮的时候，数列的状态其实已经变为有序的了。

第六轮状态：

![img][img 15]

第七轮状态：

![img][img 16]

第八轮状态：

![img][img 17]

在这种情况下，我们就不必要对这几次在重新进行排序，这样就会减少执行的次数，因此，我们可以进行一个优化，\*\*就是设置一个flags，如果已经排序了那么设置为0；如果不是有序的，那么设置为1。\*\*现在我们来看看优化后的代码。

#include<stdio.h>
    #include<stdlib.h>
     
    void BubbleSort(int a[], int len)
    { 
    	int i, j, temp;
    	int flags = 0;
    	for (j = 0; j < len - 1; j++)
    	{ 
    		for (i = 0; i < len - 1 - j; i++)
    		{ 
    			if (a[i] > a[i + 1])
    			{ 
    				temp = a[i];
    				a[i] = a[i + 1];
    				a[i + 1] = temp;
    				flags = 1;//不是有序的，flags设置为1；
    			}
    		}
    		if (flags == 0)
    			return;
    	}
    }
     
    int main()
    { 
    	int arr[] = {  5, 8, 6, 3, 9, 2, 1, 7 };
    	int len = sizeof(arr) / sizeof(arr[0]);
    	int i = 0;
    	printf("排序前：");
    	for (i = 0; i < len; i++)
    	{ 
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
     
    	BubbleSort(arr, len);
    	printf("排序后：");
    	for (i = 0; i < len; i++)
    	{ 
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }

这一个版本的代码只是做了一个小小的改动，利用fags做标记。如果在本轮排序中，元素有交换，则说明数列无序，如果没有交换，则说明数列已然有序，直接返回。

[img]: /images/20221120/ed15ead9682947429795a1ed36d383d7.png
[img 1]: /images/20221120/3a6ad297592543dc869fee2490c5423f.png
[img 2]: /images/20221120/50ee480315d149c9889c134815694072.png
[img 3]: /images/20221120/0ce2d5e2a57d4e758b19d8d0b0e936c5.png
[img 4]: /images/20221120/40a336d212724ed59e58de0cc4b59c1d.png
[img 5]: /images/20221120/7cf541b4c0c440a58173a6426501d881.png
[img 6]: https://img-blog.csdn.net/20180719165618104?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 7]: https://img-blog.csdn.net/20180719171123210?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 8]: https://img-blog.csdn.net/20180719171249134?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 9]: https://img-blog.csdn.net/20180719171439766?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 10]: https://img-blog.csdn.net/2018071917161135?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 11]: https://img-blog.csdn.net/20180719171657785?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 12]: https://img-blog.csdn.net/20180719171756529?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 13]: https://img-blog.csdn.net/2018071917183261?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 14]: https://img-blog.csdn.net/20180719171925936?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 15]: https://img-blog.csdn.net/20180719172010385?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 16]: https://img-blog.csdn.net/20180719172047975?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[img 17]: https://img-blog.csdn.net/20180719172122380?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1XzEwNzk3NzY3NTc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70