2） 折半插入排序
既然子表有序且为顺序存储结构，则插入时采用折半查找定可加速。 优点：比较次数大大减少，全部元素比较次数仅为O(nlog2n)。
时间效率：虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为O(n2) 。 空间效率：仍为 O（1） 稳 定 性： 稳定
若记录是链表结构，用直接插入排序行否？ 答：行，而且无需移动元素，时间效率更高！ 但请注意：单链表结构无法实现“折半查找”
3） 表插入排序
基本思想：在顺序存储结构中，给每个记录增开一个指针分量，在排序过程中将指针内容逐个修改为已经整理（排序）过的后继记录地址。 优点：在排序过程中不移动元素，只修改指针。 此方法具有链表排序和地址排序的特点 表插入排序算法分析：
① 无需移动记录，只需修改指针值。但由于比较次数没有减少，故时间效率仍为O(n2) 。 ② 空间效率肯定低，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元）。 ③ 稳定性：25和25*排序前后次序未变，稳定。
注：此算法得到的只是一个有序链表，查找记录时只能满足顺序查找方式。
5）希尔（shell）排序
基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。
◆ 交换排序（冒泡排序、快速排序）。
交换排序的基本思想是：两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。
1) 冒泡排序
基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。 前提：顺序存储结构
冒泡排序的算法分析：
时间效率：O（n2) —因为要考虑最坏情况
空间效率：O（1） —只在交换时用到一个缓冲单元 稳 定 性： 稳定 —25和25*在排序前后的次序未改变
冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一个元素的位置（挤出一个泡到表尾），还可以对前面的元素作一些整理，所以比一般的排序要快。
2） 快速排序
基本思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。
优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！ 前提：顺序存储结构
时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加
空间效率：O（log2n）—因为递归要用栈(存每层low，high和pivot) 稳 定 性： 不 稳 定 —因为有跳跃式交换。
◆ 选择排序（简单选择排序、树形选择排序、堆排序）。 选择排序的基本思想是：每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i 个记录。 1）简单选择排序
思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。
——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；?如此进行下去，直到全部有序为止。 优点：实现简单
缺点：每趟只能确定一个元素，表长为n时需要n-1趟 前提：顺序存储结构
Void SelectSort(SqList &L ) { for (i=1; i 2）锦标赛排序 (又称树形选择排序) 基本思想：与体育比赛时的淘汰赛类似。 首先对 n 个记录的关键字进行两两比较，得到 ?n/2? 个优胜者(关键字小者)，作为第一步比较的结果保留下来。然后在这 ?n/2? 个较小者之间再进行两两比较，?，如此重复，直到选出最小关键字的记录为止。 优点：减少比较次数，加快排序速度 缺点：空间效率低 3）堆排序 1.堆的定义：设有n个元素的序列 k1，k2，?，kn，当且仅当满足下述关系之一时，称之为堆。 解释：如果让满足以上条件的元素序列 （k1，k2，?，kn）顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。 2. 怎样建堆？ 步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。 堆排序算法分析： 时间效率： O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust( )算法，而算法本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。 学习要点： ◆ 各种排序所基于的基本思想。 ◆ 在“最好”和“最差”情况下，排序性能的分析，是否是稳定排序的结论，时间效率和空间效率。 ◆ 对每种排序方法的学习，应掌握其本质（排序所基于的思想），熟练掌握手工模拟各种排序的过程。 补充： 1.排序算法的好坏如何衡量？ 时间效率——排序速度（即排序所花费的全部比较次数） 空间效率——占内存辅助空间的大小 稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。 2.“快速排序”是否真的比任何排序算法都快？ ——基本上是，因为每趟可以确定的数据元素是呈指数增加的。