排序6：冒泡排序及优化思想

目录

排序思想

动图演示

代码实现

优化

总结

---

 

排序思想

通过逐一比较以及交换，将大的数向序列的尾部移动，将小的数向序列的头部移动。逐渐缩小范围，已经排好的数字就不需要再排，最后直到每一个数字都排到了正确的位置。

 

动图演示

  

代码实现

逻辑：排序思想我们可以了解到，实现一定是需要双重循环的：

第一层循环来控制轮数，第二层循环来控制单轮中所有需要排序的数字的排序。

第一层循环：每一轮能够使得一个数字排好，那么n个元素就需要n - 1轮，因为如果n - 1个元素都正确归位了，那么最后一个也一定在正确的位置上。

我们可以使用一个for循环，其中设置一个int 类型的变量i ，i从0开始，一直到n - 1。

第二层循环：n个元素需要比较n - 1次才能取出最大值，每一轮都能比较出一个需要排序的数字组中的最大数字，所以每一次轮需要排的数字就会减少一个，最后减少到0为止。

在第一轮，排n -1次，第二轮，排n - 2 次，第三轮，排n - 3 次……我们可以知道排的次数与轮数也有关系。

最后是关于比较，我们比较某个元素与后面一个元素的大小，如果前面的大于后面的元素，那么两个元素就交换值。比较持续到第n - 1个。（这里最容易发生越界问题，有些人会比较到第 n 个与第n + 1 个）

所以我们第二层循环也用一个for循环 ，其中设置一个int 类型的变量 j ，j 从0开始，j < n - i -1，j 代表了元素的下标。

代码如下：

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

  

优化

上面代码虽然有了，但是我们会发现，如果排一半数组已经有序了，还是会反复进行比较，影响效率。

因此，我们可以设置一个判断值exchange来进行优化。我可以设置当exchange的值为0，当进行了交换元素的值的时候，说明进行了排序，那么将exchange的值改为 1，如果结束一轮的时候exchange == 1，我们继续排序，如果是exchange == 0，那么直接结束排序，没轮开始都需要将exchange重置为0。

代码：

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		int exchange = 0;
		for (int j = 0; j < n - i - 1; ++j)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}

 

总结

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1)

4. 稳定性：稳定