第9章排序9.1概述什么是排序假设含n个记录的序列为{R1,R2,…，Rn},其相应的关键字序列为{K1,K2,…，Kn}内部排序和外部排序内部排序的方法基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：（1）插入类（2）交换类（3）选择类（4）归并类（5）基数排序内排序过程有两种基本操作：比较两个关键字的大小；将记录从一个位置移到另一个位置评价排序算法优劣的标准：(1)算法的运算量(记录关键字的比较次数和移动记录的次数)；(2)执行算法所需要的辅助存储单元空间(3)算法本身的稳定性数据类型定义:插入排序实现“一趟插入排序”可分三步进行：1直接插入排序（基于顺序查找）直接插入排序(2)对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动，即for(j=i-1;R[0].key<R[j].key;--j)R[j+1]=R[j];第9章排序voidInsertionSort(SqList&L){//对顺序表L作直接插入排序for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key){}}//InsertSort内部排序的时间分析：最好的情况（关键字在记录序列中顺序有序）：折半插入排序voidBiInsertionSort(SqList&L){}//BInsertSortlow=1;high=i-1;while(low<=high){}折半插入排序算法与直接插入排序算法相比，仅减少了关键字比较次数，而记录移动次数不变，所以时间复杂度为O(n2)基本思想是另设一个数组d，将R[1]赋给d[1]，并将d[1]看成是排序后的中间记录，从第二个记录开始一次将关键字小于d[1]的记录插入到d[1]之前的有序序列，将关键字大于d[1]的记录插入到d[1]之后的有序序列。交换排序起泡排序假设在排序过程中，记录序列R[1..n]的状态为：第9章排序voidBubbleSort(Sqlist&R){}//BubbleSort时间分析:快速排序一趟快速排序的具体做法是：设立两个指针low和high，它们的初值分别为s和t，之后逐渐减小high，增加low，并保证R[high].key≥pivotkeyR[low].key≤pivotkey否则进行记录的“交换”。一趟快速排序算法描述如下：intPartition(SqList&R,intlow,inthigh){pivotkey=R.r[low].key;//枢轴记录的关键字while(low<high){while(low<high&&R.r[high].key>=pivotkey)--high;//将比枢轴记录小的记录交换到低端R.r[low]←→R.r[high];while(low<high&&R.r[low].key<=pivotkey)++low;//将比枢轴记录小的记录交换到低端R.r[low]←→R.r[high];}returnlow;//返回枢轴所在位置}//PartitionintPartition1(SqList&R,intlow,inthigh){}//Partition快速排序voidQSort(SqList&R,ints,intt){//对记录序列R[s..t]进行快速排序if(s<t){//长度大于1}}//QSortvoidQuickSort(SqList&L){//对顺序表进行快速排序QSort(L.r,1,L.length);}//QuickSort将关键字序列45，33，50，86，72，10，20，45进行快速排序的全过程如图9-10所示：快速排序的时间分析若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。快速排序是一种不稳定的排序方法选择排序假设排序过程中，记录序列已经分成有序序列R[1..i-1]和无序序列R[i..n]两部分，一趟简单选择排序就是从无序序列R[i..n]中选择关键字最小的记录，直接放在有序序列R[1..i-1]的后面，得到长度增加1的有序序列R[1..i]。简单选择排序的算法描述如下:voidSelectSort(SqList&R){//对记录序列R作简单选择排序。for(i=1;i<R.length;++i){//选择第i小的记录，并交换到位}}//SelectSort时间性能分析简单选择排序是不稳定的排序方法堆排序若将此序列对应的一维数组看成一个完全二叉树，则堆的含义表明：完全二叉树中所有非终端节点的值均不大于（或不小于）其左、