你真的了解冒泡排序吗？

快来打我* 2022-04-24 09:14 301阅读 0赞

## 冒泡排序 ##

顾名思义，冒泡排序就像吐泡泡一样，泡泡会越来越大，对应我我们的排序算法中，就是将我们的最大数沉淀。说到泡泡。。。 不由得让我想起了网红语~~~ 香啊、造啊、香皂啊，吃完吐泡泡。 哈哈！

**基本原理**

*  冒泡排序是一种交换排序的简单排序算法，它是将相邻的两个元素比较，将比较大的元素向后移动，较小的元素向前，类似于我们的冒泡泡，所以冒泡排序就诞生了，它的思想比较简单，易理解，很适合于初学者学习。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]

**冒泡排序一**

//冒泡排序基础版
    void BubbleSort1(int array[], int size)
    {
    	for (int i = 0; i < size; i++)
    	{
    		for (int j = 0; j < size - i - 1; j++)
    		{
    			if (array[j] > array[j + 1])
    			{
    				int temp = array[j];
    				array[j] = array[j + 1];
    				array[j + 1] = temp;
    
    			}
    		}
    	}
    }

此版本什么都不考虑，直接进行排序

**冒泡排序二**

//冒泡排序
    void BubbleSort2(int array[], int size)
    {
    	for (int i = 0; i < size; i++)
    	{
    		//假设数组有序
    		int sorted = 1;
    		for (int j = 0; j < size - i - 1; j++)
    		{
    			if (array[j] > array[j + 1])
    			{
    				int temp = array[j];
    				array[j] = array[j + 1];
    				array[j + 1] = temp;
    				sorted = 0;
    
    			}
    		}
    		if (sorted == 1)
    		{
    			return;
    		}
    	}
    }

该版本较容易理解，假如我们排完几趟之后，数列已经有序，直接退出。设置一个标志位即可，通俗易懂。

**冒泡排序三**

//冒泡排序三
    void BubbleSort3(int array[], int size) {
    	int j, k;
    	int flag = size;
    	while (flag > 0) {
    		k = flag;
    		flag = 0;
    		for (j = 1; j < k; j++) {
    			if (array[j - 1] > array[j]) {
    				int tmp = array[j - 1];
    				array[j - 1] = array[j];
    				array[j] = tmp;
    				flag = j;
    			}
    		}
    	}
    }

该版本应用于假如有50个数，只有前5个无序，后45个已经有序且都大于前5个数，那么我们每次只需要遍历到最后发生交换的位置即可，后45个数完全不用遍历，节省了不少时间。

**总结**

*  关于冒泡排序它的效率还是比较低下的，如果要排序的数字规模很大，建议用其它排序方法。
 *  时间复杂度 O(n2)
 *  空间复杂度 O(1)
 *  稳定性： 稳定

小小的冒泡其实也没有那么简单，两种简单变形你都懂了吗？

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20220217/8fdc15f76a874b24ba284684c5e5cc48.png