Bubble Sort

Posted on | In ,

Before Starting

从开博客至今已经很久了，然而到现在为止也只有一篇 ‘Hello world’，一直想找点什么东西写但是又太懒，也就一直拖着不动。这几天忽然想起来要复习一下快忘光的数据结构，所以干脆从这个开始写博客，也算强迫自己做些笔记。

数据结构和算法之前想买本 Algorithm, 4th Edition 来看，但是实在 看不懂 看得太慢，所以还是选择先把 VisuAlgo.net 用 C++ 简单实现一遍，于是就有了这篇博客。

Bubble Sort

冒泡排序（bubble sort）是一种简单的排序算法，其基本原理是每次遍历一遍未排序的数列，依次比较未排序部分中相邻的两个元素，并使这两个元素按正确顺序排列，如此重复至所有元素都按正确顺序排序。很显然，每次遍历数列中未排序的部分，其结果就是将未排序部分的最小（最大）元素移动到数列的一端。

对于有$n$个元素的数列来讲，排序的最坏情况就是逆序数列，此时的时间复杂度为$O(n^2)$，而当数列是已经排好序的序列时，算法有最优时间复杂度为$O(n)$. 算法的平均时间复杂度为$O(n^2)$.

Code

VisuAlgo.net上给的冒泡排序的伪代码如下：

1
2
3
4
5
6
7
do
	swapped = false
	for i = 1 to index_of_last_unsorted_element - 1
		if left_element > right_element
			swap(left_element, right_element)
			swapped = true
while swapped

下面是C++代码的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubble_sort(vector<int>& vec)
{
	bool swapped = false;
	int unsorted = vec.size();
	do {
		swapped = false;
		for (int i = 1; i < unsorted; ++i)
			if (vec[i] < vec[i - 1]) {
				swap(vec[i], vec[i - 1]);
				swapped = true;
			}
		--unsorted;
	} while (swapped);
}