Blog

JerryZRF的Blog

算法-排序-冒泡

发表于 更新于 分类于

算法-排序

前言

有人可能会说，STL库中不是有sort函数吗，为什么还有学排序呢？
因为排序的基本算法还有很多功能，如快速排序的求第k小(大)的数、插入排序的一元多项式等等。

1 冒泡排序

特点

  • 简单(至少我个人认为)
  • 稳定(你也许没听懂)

简介

冒泡排序，顾名思义，小的数据像泡泡一样向上(前)浮(移动).

演示

原始数据(8个)
7 4 8 3 2 5 1 6

第一次排序
4 7 3 2 5 1 6 8

第二次排序
4 3 2 5 1 6 7 8

第三次排序
3 2 4 1 5 6 7 8

第四次排序
2 3 1 4 5 6 7 8

第五次排序
2 1 3 4 5 6 7 8

第六次排序
1 2 3 4 5 6 7 8

演示解析

从数据变化中我们可以看出，小的数据一直再向前走，大的数据一直在向后走，就像泡泡一样，向上浮。

实现

Version 1 基本版本

1
2
3
4
5
6
7
8
9
10
11
12
13
void Sort(int array[], int num)
{
	for(int i = 0; i < num; i++)               //需要走num遍排序
	{
		for(int j = 0; j < num - 1; j++)       //从0比较到num-1
		{
			if(array[j] > array[j + 1])        //和后面一个数比较
			{
				swap(array[j], array[j + 1]);  //交换
			}
		}
	}
}

在这个版本中，我们可以看到需要走num遍排序，时间复杂度是O(num^2)。而像演示一样的情况中，后面两次其实是不用走到，所以我们就要一个判断，判断数据是否已经有序。

Version 2 改进版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Sort(int array[], int num)
{
	bool flag;
	for(int i = 0; i < num; i++)
	{
		flag = true;                              //是否有序
		for(int j = 0; j < num - 1; j++)
		{
			if(array[j] > array[j + 1])           //更小
			{
				swap(array[j], array[j + 1]);     //交换
				flag = false;                     //依旧无序
			}
		}
		if(flag == true)                          //已经有序
			break;                                //跳出循环
	}
}

有了有序特判，算法的性能有了小幅提高。

END

冒泡排序还是一种比较简单的排序方法，接下来还有选择、插入、快速、堆、桶排序等。