最简单的冒泡排序是通过一次次地比较交换，使得待排序区间的一个个最大元素就位。
其最坏、平均时间复杂度为O(n2)，然而最好却可以达到O(n)的线性时间复杂度。
冒泡排序最大的一个弊端就是交换次数太多。如果元素的 swap 操作比较费时，这个问题将更为突出。

那么能否减少元素间的交换，使得每个区间的最大元素可以一次就位呢？引入选择排序。
选择排序每次从待排序区间选取最大元素，然后直接就位，有效地减少了交换操作。
其最坏、平均复杂度均为O(n2)。然而很不幸地是，其最好时间复杂度也是O(n2)。
冒泡排序最优的线性时间复杂度在选择排序中将无法保持。

接着是否既可以减少交换操作又同时可以做到最优为O(n)呢。插入排序可以做到。
插入排序将待排序区间的每个元素依次寻找合适位置插入到已排序区间。
其时间复杂度约等于带排序向量的逆序对数，因此最坏和平均时间复杂度为O(n2)。
其最好时间复杂度可以像冒泡排序一样做到O(n)的线性时间复杂度。
然而，很不幸地是，插入排序只适合链表，而不适合数组。

归并排序是分治算法的典型应用。
它把问题分为两个较小的子规模，分别求解，然后再合并。
其优点很明显，算法时间复杂度固定为O(nlogn)，无论最好、最坏、还是平均，很稳定。
并且归并排序也是高级排序算法中为数不多的稳定性排序算法。
归并排序的问题在于空间复杂度，其空间复杂度高达O(n)。

接下来的堆排序与选择排序很相似。
记得在选择排序中，每次最大元素的选取需要消耗O(n)的时间，n 为带排序区间长度。
而堆排序中利用堆结构，最大元素的选取操作可以做到O(logn)。
其最坏、平均、最优时间复杂度均为O(nlogn)。
与归并排序对比，其空间复杂度可以做到O(1)，代价是堆排序是不稳定的。

快速排序与最原始的冒泡排序有着一定的渊源。
冒泡排序每次选择在最终结果中已经就位的一个个最大元素；
快速排序不限于最大元素，而是一个个轴点，冒泡排序可以视作为快速排序的一个特例。
快速排序的平均、最好时间复杂度为O(nlogn)，并且名副其实，快速排序有着较小的常系数。
同时快速排序也可以做到in-place 就地算法，空间复杂度O(1)。
其缺点在于最坏时间复杂度为O(n2)，虽然几率很小。同时也是不稳定的。