常见排序算法

选择排序

思想：将待排序数组分为已排序和未排序两个部分。每次从未排序部分里面选择最小的，append到已排序部分。重复直至未排序部分为空。

SelectionSort(A)
	For i = 1 to n do
		Sort[i] = Find-Minimum from A
		Delete-Minimum from A
	Return(Sort)

从 1 遍历到 n，是 $O (n)$ 的。从未排序部分找最小值也是 $O (n)$ 的。所以选择排序的时间复杂度是 $O (n^{2})$ . 如果我们能利用某种数据结构，在 $O (lo g n)$ 时间找到最小值，算法复杂度就能降到 $O (n lo g n)$ .

哈哈，这次第二个就介绍堆排序，因为我就是为了学习堆而写的这篇笔记。

竖起耳朵听好了，

Heapsort is nothing but an implementation of selection sort using the right data structure.

— The Algorithm Design Manual