十四、排序（Sort） 这可能是最有趣的一节。排序的考题，在各大公司的笔试里 最喜欢出了，但我看多数考得都很简单，通常懂得冒泡排序就差不多了，确实，我在刚学数据机构时候，觉得冒泡排序真的很“精妙”，我怎么就想不出呢？呵呵， 其实冒泡通常是效率最差的排序算法，差多少？请看本文，你一定不会后悔的。 1、冒泡排序（Bubbler Sort） 前面刚说了冒泡排序的坏话，但冒泡排序也有其优点，那就是好理解，稳定，再就是空间复杂度低，不需要额外开辟数组元素的临时保存控件，当然了，编写起来也容易。 其算法很简单，就是比较数组相邻的两个值，把大的像泡泡一样“冒”到数组后面去，一共要执行N的平方除以2这么多次的比较和交换的操作（N为数组元素），其复杂度为Ο (n²)，如 图 ： 2、直 接 插 入 排序（Straight Insertion Sort） 冒 泡法对 于 已 经 排好序的部 分 （上 图 中 ，数组显 示 为白 色 底 色 的部 分 ）是不再访 问 的，插 入 排序却 要，因 为它 的方法就是从 未 排序的部 分 中 取 出一个元素，插入 到已 经 排好序的部 分 去，插 入 的位 置 我是从 后往 前找 的，这样可以使 得如 果数组本身 是有序（顺 序）的话，速 度会非 常之 快 ，不过 反 过 来，数组本身 是逆 序的话，速 度也就 非 常之 慢 了，如 图 ： 3、二分插入排序（Binary Insertion Sort） 这 是对直接插入排序的改进，由于已排好序的部分是有序的，所以我们就能使用二分查找法确定我们的插入位置，而不是一个个找，除了这点，它跟插入排序没什么区 别，至于二分查找法见我前面的文章（本系列文章的第四篇）。图跟上图没什么差别，差别在于插入位置的确定而已，性能却能因此得到不少改善。（性能分析后面 会提到） 4、直接选择排序（Straight Selection Sort） 这是我在学数据结构前，自己能够想得出来的排序法，思路很 简单，用打擂台的方式，找出最大的一个元素，和末尾的元素交换，然后再从头开始，查找第 1个到第 N-1个元素中最大的一个，和第 N-1个元素交换„„其实 差不多就是冒泡法的思想，但整个过程中需要移动的元素比冒泡法要少，因此性能是比冒泡法优秀的。看图： 5、快速排序（Quick Sort） 快速排序是非常优秀的排序算法，初学者可能觉得有点难理解，其实它是一种“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的，所以你一会...
