内部排序

　　考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标(时间复杂度)能否了如指掌。

　　排序方法分类有：插入、选择、交换、归并、计数等五种排序方法。

　　(1)插入排序中又可分为：直接插入、折半插入、2路插入(?)、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找，希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。

　　(2)交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。

　　(3)选择排序可以分为：简单选择、树选择、堆排序。选择排序相对于前面几种排序算法来说，难度大一点。这三种方法的不同点是，根据什么规则选取最小的数。

　　简单选择，是通过简单的数组遍历方案确定最小数;

　　树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大(小)者，最终选出最小(大)数;

　　而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。

　　(4)归并排序，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。

　　(5)基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序(扑克牌排序)，链式排序(整数排序)。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。

　　本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的。

　　//////////////////////////////////////////////稳定性分析////////////////////////////////////////////////

　　排序算法的稳定性，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

　　稳定性的好处：若排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)。