选择排序（Selection sort） 是一种非常简单且直观的排序算法，其主要思路是将数列中未排序部分的最小（大）元素与起始位置的元素进行交换，并放入已排序部分的末尾，直到完成排序。当未排序部分的第一个元素即为最小（大）元素时，算法仍然需要将该元素与未排序部分中的所有元素依次比较大小；而每次交换则至少有一个元素被放在正确位置，也就是说，对于一个有$N$个元素的数列，实际发生的交换次数最多为$N - 1$. 因此，算法性能是由数列元素的比较次数所决定的。对于一个有$n$个元素的数列来说，选择排序算法的时间复杂度总是$O(n^2)$. 总的来说，选择算法排序有两个明显特点：

• 运行时间与输入无关。无论输入数列是顺序的还是需要交换次数最多的，算法的时间复杂度都不变，仅与数列元素个数有关。
• 数据移动次数最少。对数列元素的交换次数和数列元素个数是线性关系。

举个例子，我们使用选择排序算法对数列$ \lbrace 4, 5, 3, 1, 2\rbrace $进行排序：

Codes

伪代码：

1
2
3
4
5
6

repeat (num_of_elements - 1) times
	set the first unsorted element as the min
	for each of the unsorted elements
		if element < current_minimum
			set element as new minimum
	swap minimum with first unsorted position

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12

void selection_sort(vector<int> vec)
{
	int len = vec.size();
	for (int i = 0; i < len - 1; ++i) {
		int min_pos = i;
		for (int j = i + 1; j < len; ++j) {
			if (vec[j] < vec[min_pos])
				min_pos = j;
		}
        swap(vec[min_pos], vec[i]);
	} 
}

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);
}

This is the very first post of the blog.

Build on Feb. 27, 2018.