算法-排序-冒泡

算法-排序

前言

有人可能会说,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

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