第9章典型排序算法第9章典型排序算法9.1实例：统计学生成绩表9.1.1问题描述9.1.2问题分析9.1.3实现算法9.1.4排序定义及相关概念structRtype//排序记录{KeyTypekey;//关键字域┆};#definemaxlenmaxsize//分配的存储单元个数structListSq//顺序表{Rtypee[maxlen];//0号单元空闲intlen;}9.2插入排序9.2.1直接插入排序直接插入排序的实现算法：（略）时间复杂度：最好情况是原始记录已按关键字递增有序排列，整个排序过程的比较次数为n-1次，时间复杂度为O(n)。最坏情况是原始记录按关键字递减有序排列，整个排序过程的比较次数为(n+2)(n-1)/2，记录移动的次数为(n+4)(n-1)/2，时间复杂度是O(n2)。平均情况下，时间复杂度是O(n2)。直接插入排序是一种稳定的排序方法。9.2.2折半插入排序9.2.3希尔排序9.3选择排序9.3.1直接选择排序9.3.2堆排序堆排序需要解决的两个问题：1如何将一个无序序列建成一个堆?2在输出堆顶元素之后，如何将剩余元素调整为一个新的堆?一个无序序列建成一个堆的过程：是一个反复“筛运算”的过程。先将待排序序列按顺序构造成一棵完全二叉树，然后对完全二叉树中的所有非终端结点进行调整。按完全二叉树中结点的编号顺序来讲，最后一个非终端结点是第个元素，由此“筛运算”只需从第个元素开始，一直调整到根结点。调整原则：根据堆的定义，使得所的的双亲结点与它的孩子结点都满足堆定义，不满足时结点间进行交换。将剩余元素调整为一个新堆的过程：输出堆顶元素之后，以堆中最后一个元素来替代根结点。此时根结点的左、右子树均为堆，则仅需自上至下进行调整即可。首先将堆顶元素与其左、右子树根结点的值进行比较，若不满足堆的定义，进行结点间的交换，继续往下调整，直到叶子结点。堆排序的实现算法：（略）时间复杂度：每次筛运算的时间复杂度为O(log2n)，整个堆排序的时间复杂度为O(n)，是一种不稳定的排序方法。9.4交换排序9.4.1冒泡排序冒泡排序的实现算法：（略）在排序过程中，如果某一趟排序中不存在相邻元素的交换，意味着待排序序列已有序，无需进行下一趟排序。所以，在算法中设置了一个标志flag，初值为1，每一趟排序开始时，都将标志flag的值设置为0，只有在比较过程中存在元素交换时，才把标志flag的值设为1。时间复杂度：时间复杂度为O(n2)，是一个稳定的排序方法。9.4.2快速排序快速排序的实现算法：（略）时间复杂度：快速排序的时间复杂度为O(nlogn)，是一种不稳定的排序方法。9.5归并排序和基数排序9.5.1归并排序二路归并排序的实现算法：（略）时间复杂度：二路归并排序的时间复杂度为o(n)，是一种稳定的排序方法。9.5.2基数排序9.6比较各种内排序方法从稳定性比较直接插入排序、折半插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，而直接选择排序、堆排序、快速排序和希尔排序是不稳定的排序方法。从算法的简单性比较直接插入排序、折半插入排序、直接选择排序和冒泡排序都是简单排序方法，排序过程易于理解、实现算法也简单。而快速排序、希尔排序、堆排序和归并排序等是前面几种简单排序的一种改进型排序方法，所以相对来讲，实现算法较复杂一些。各种内排序方法的选择：影响选择排序方法的因素在选取合适的排序方法时需要考虑以下因素：(1)待排序的元素数目n；(2)记录本身信息量的大小；(3)排序方法的稳定性；(4)辅助空间的大小等。在选取排序方法时，首先应考虑排序稳定性，其次考虑待排序记录数n的大小，从而选取适当的排序方法。(1)若n较小(n<=30)，则可以采用直接插入排序或直接选择排序。(2)若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。(3)若n较大，应采用快速排序、堆排序或归并排序等。(4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，由此得：当n个关键字随机分布时，借助"比较"的排序算法，至少需要O(nlog2n)的时间。(5)当记录本身信息量较大时，可用链表作为存储结构。9.7外排序9.7.1外排序的基本过程外部排序所需总时间=内部排序（产生初始归并段）所需的时间m*tis+外部信息读写的时间d*tio+内部归并所需的时间s*utmg其中：tis是为得到一个初始归并段进行内部排序所需时间的均值tio是进行一次外存读/写时间的均值utmg是对u个记录进行内部归并所需时间m为经过内部排序之后得到的初始归并段的个数s为归并的趟；d为总的读/写次数9.7.2多路归并排序（