一、考试内容：

1，排序的基本概念， 

排序又称分类，排序是将一组杂乱无章的“无序”的记录序列调整为按其关键字的顺序排列起来的“有序”的记录序列。

排序方法分类的依据；  排序的依据可以是记录的主关键字，也可以是次关键字，甚至是若干数据项的组合。为了讨论方便把排序所依据的数据项统称排序关键字，简称关键字

稳定性   假设在一组记录中ki=kj（i<j），且在排序之前的序列中Ri领先于Rj，通过排序算法重新排序后的序列中Ri仍领先于Rj，则称这个排序算法是稳定的，否则就是不稳定的。

2，各种常用的排序方法。

（1）插入排序、 将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。

--1直接插入排序(straight insertion sort)

    直接插入排序是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为m(假设)的有序表中，使之仍保持有序，从而得到一个新的长度为m＋1的有序表。    

--2折半插入排序（Binary Insertion sort）  

操作和直接插入排序类似，只是在查找插入位置时采用折半法查找。

空间：需要一个记录的辅助空间

时间：关键字的比较次数由于采用了折半查找而减少，数量级为O(nlog2n)，移动次数与直接插入排序相同,仍为O(n2) ，故时间复杂度为O（n2）

--3希尔排序(shell sort)

初期选用大跨步(增量较大)间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为1，这样记录移动次数大大减少，提高了排序效率。 希尔排序对增量序列的选择没有严格规定。  不稳定

（2）交换排序、  通过“交换”无序序列中的记录，从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。

--1  冒泡排序  

冒泡排序(bubble sort)是一种人们熟知的、最简单的交换排序方法。在排序过程中，关键字较小的记录经过与其他记录的对比交换，像水中的气泡向上冒出一样，移到序列的首部，故称此方法为冒泡排序法。    稳定

--2  快速排序  

它是一种对冒泡排序的改进。由于其排序速度快，因此称快速排序(quick sort)。快速排序通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行快速排序，以达到整个序列有序。

（3）选择排序、  记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中。

--1  简单选择排序   

简单选择排序(simple selection sort)也是直接选择排序，是一种较为容易理解的方法。

基本思想：  每一趟在n-i+1(i=1,2,…,n-1)个记录中,通过n-i次的关键字比较，选取关键字最小的记录与有序序列中的第i个记录交换。   稳定

--2  堆排序(heap sort)  

 除了简单选择排序之外，还有树形选择排序(锦标赛排序)，1964年威洛姆斯(J.Willioms)提出了进一步改进的排序方法，即堆排序(heap sort)。

堆排序的步骤： 1）由一个无序序列建成一个堆   按照完全二叉树的特点将无序序列建成一棵完全二叉树，该完全二叉树的最后一个非终端结点是第n/2个元素。先取i=n/2(它一定是第n个结点双亲的编号)将以i结点为根的子树调整为堆；然后令i=i-1，再将以i结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。

2) 堆排序    首先输出堆顶元素(一般是最小值)，让堆中最后一个元素上移到原堆顶位置，然后恢复堆，因为经过上移堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；此时根结点的左、右子树均为堆，则仅需自上而下调整即可。把刚才这个自堆顶至叶子的调整过程为“筛选” 。重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤，直到全部元素输出完为止。    不稳定

（4）归并排序、  通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。

--两路归并排序算法思路：1) 把n个记录看成n个长度为1的有序子表；2) 进行两两归并使记录关键字有序，得到n/2个长度为2的有序子表；3) 重复第2)步直到所有记录归并成一个长度为n的有序表为止。

（5）基数排序

排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

使用到桶 (Bucket)，顾名思义，通过将要比较的位（个位、十位、百位…），将要排序的元素分配至 0~9 个桶中，借以达到排序的作用，在某些时候，基数排序法的效率高于其它的比较性排序法。

链式基数排序  使用链表将每次的比较的结果用指针链接到后面。

总结上述排序的评价

二、考试要求：

了解排序的定义及术语，

排序方法的评价方法，

掌握的排序方法有：直接插入排序、shell插入排序，快速排序，堆排序，二路归并排序，链式基数排序，要知道它们的排序思想，并能描述排序过程。