数据结构复习要点第八章排序

记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。
排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作：比较关键字大小；改变指向记录的指针或移动记录。
 ·存储结构：顺序结构、链表结构、索引结构。
经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的，否则排序算法是不稳定的。
排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序)，反之，若存在数据的内外存交换，则称之为外排序。
内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。
评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。

插入排序：·直接插入排序： ·逐个向前插入到合适位置。
·哨兵(监视哨)有两个作用： ·作为临变量存放R[i]
·是在查找循环中用来监视下标变量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)的排序方法；
·记录的大小(规模)；记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现；
·关键字的结构及其初始状态；
·对稳定性的要求；
·语言工具的条件；
·存储结构；
·时间和辅助空间复杂度