2019考研计算机：数据结构知识点整理（8）

考研网

下面是新东方在线整理的2019考研计算机专业课资料：数据结构的知识点整理，请参考：
        第八章 排序知识点整理
    记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。
    排序是使文件中的记录按关键字递增(或递减)次序排列起来。
    ·基本操作：比较关键字大小;改变指向记录的指针或移动记录。
    ·存储结构：顺序结构、链表结构、索引结构。
    经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。
    排序过程中不涉及数据的内、外存交换则称之为“内部排序”(内排序)，反之，若存在数据的内外存交换，则称之为外排序。
    内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。
    评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。
    插入排序：·直接插入排序： ·逐个向前插入到合适位置。
    ·哨兵(监视哨)有两个作用： ·作为临变量存放R     ·是在查找循环中用来监视下标变量j是否越界。
    ·直接插入排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为(n+2)(n-1)/2;移动次数为(n+4)(n-1)/2;
    ·希尔排序： ·等间隔的数据比较并按要求顺序排列，最后间隔为1.
    ·希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25)，比较次数为(n^1.25);移动次数为(1.6n^1.25);
    交换排序：·冒泡排序：·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个，后自上向下确定最重的一个。
    ·冒泡排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为n(n-1)/2;移动次数为3n(n-1)/2;
    ·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。
    ·快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n)，比较次数为n(n-1)/2;
    选择排序：·直接选择排序： ·选择最小的放在比较区前。
    ·直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2;
    ·堆排序 ·建堆：按层次将数据填入完全二叉树，从int(n/2)处向前逐个调整位置。
    ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。
    ·堆排序是就地不稳定的排序，时间复杂度为O(nlog2n)，不适宜于记录数较少的文件。
    归并排序： ·先两个一组排序，形成(n+1)/2组，再将两组并一组，直到剩下一组为止。
    ·归并排序是非就地稳定排序，时间复杂度是O(nlog2n)，
    分配排序：·箱排序： ·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。
    ·箱排序的平均时间复杂度是线性的O(n)。
    ·基数排序：·从低位到高位依次对关键字进行箱排序。
    ·基数排序是非就稳定的排序，时间复杂度是O(d*n+d*rd)。
    各种排序方法的比较和选择： ·待排序的记录数目n;n较大的要用时间复杂度为O(nlog2n)的排序方法;
    ·记录的大小(规模)：记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现;
    ·关键字的结构及其初始状态：    ·对稳定性的要求;
    ·语言工具的条件：     ·存储结构;    ·时间和辅助空间复杂度。