学习目标

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

知识要点

（1）掌握几种基本排序的排序思想、排序过程、算法及其依据的原则。

（2）掌握各种排序算法的时间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O（n2）的简单排序方法、O（nlog2n）的高效排序方法和O（d×n）的基数排序方法。

（3）理解排序方法稳定和不稳定的含义。

（4）希尔排序、快速排序、堆排序和归并排序等高效方法是本章学习的重点和难点。