内部算法性能分析 第4章 详细设计
再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。
大根堆排序算法的基本操作：
初始化操作：将R[1..n]构造为初始堆；
每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
算法：
for(i=(L/2);i>=1;i--)//将二叉树转换成堆 CreateHeap(i,L);//建堆
for(i=L-1,k=1;i>=1;i--,k++)
{
temp=R[i+1];//堆（heap）的root值和最后一个值交换 R[i+1]=R[1];
R[1]=temp; changes+=3;
}
CreateHeap(1,i);
从上述分析：堆[排序的时间，主要由建立初始]堆和反复重建堆这两部分的时间开销构成，它们均是通过调用CreateHeap实现的。
堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)，由它是不稳定的排序方法。
17
内部算法性能分析 第4章 详细设计
4.7六种排序方法讨论
综合比较上述的各种内部排序方法，大致有如下结果（见下表）
表4.1
排序方法 直接插入排序 简单选择排序 n(n-1)/2 n*(n-1)/2 简单 快速排序 O(nlogn) n*(n-1)/2 ) O(nlognn(n-1)/2 O(n*n) O(nlogn) O(nlogn) O(logn) 是 较复杂 希尔排序 冒泡排序 堆排序 O(nlogn) 复杂 简单 较较
n-1 (n+2)(n-1)/2 最少比较次数 最多比较次数 最少移动次数 最多移动次数 最坏情况 时间复杂度 最好情况 平均情况 空间复杂度 稳定复杂性 度 简单 0 n+4(n-1)/2 O(n*n) O(n) O(n*n) O(1) 是 0 3(n-1) O(n*n) O(n*n) O(n*n) O(1) 否 O(nlogn) O(nlogn) O(1) 否 n-1 n*(n-1)/2 0 n(n-1)/2 O(n*n) O(n) O(n*n) O(1) 是 O(nlogn) O(nlogn) O(nlogn) O(1) 否 复杂 附注：
1、 堆排序、冒泡排序、希尔排序和快速排序中，在待排序的数据已经基本
有序是，花费时间最多的反而是快速排序，此是最不利于发挥其特长。 2、 在以比较为基础的排序方法中，“比较关键字的大小”和“将关键字从
一个位置移动到另一个位置”这两种操作的次数决定了算法的时间复杂性，它们是算法的时间复杂性的两项指标。
3、 在局部有序和待排序的关键字序列数目较小时，最佳的内部排序方法是
直接插入排序。
4、 在冒泡排序的每一趟中，只能将关键字最大或最小的元素移动到正确的
置，其他关键字有可能在交换的过程中朝着与最终排序相反方向移动；快速排序的每一趟中，不仅能将枢轴的元素移动到正确的位置，而且其他关键字所移动的方向也与其最终排序的位置方向一致。
5、 设有一个堆，取出堆中最大元素后，将它重新调整为堆，所需要的时间
18
内部算法性能分析 第4章 详细设计
复杂度为O(nlogn)
6、 假设待排序的关键字序列有n（例如，n=10000）个元素，若仅找出其中
最大的k（例如k=10）个元素，则采有堆排序最省时间；若仅找出其中第k个最小元素，则采用快速排序最省时间
如何选择好的排序方法：
没有哪一种排序方法是绝对好的。每一种排序方都有优缺点，适合于不同的环境。因此，在实际应用中，应根据具体情况进行选择。首先，考虑排序对稳定性的要求，若要求稳定，则只能在稳定的排序方法中选取，否则可以在所有的方法中选取；其次要考虑待排序列的记录数目n，若n较大，则可以在改进的方法中选取，否则在简单方法中选取；然后再考虑其他因素。综上所述，可得以上结论：
1、当待排序的序列的记录数目n较大，记录按关键字的值分布比较随机，并且对排序稳定必不作要求时，宜选用快速排序。
2、当待排序的序列的记录数目n较大，记录按关键字的值分布可能出现升序或逆序的情况，并且对排序稳定性不作要求时，宜选用堆排序。
3、当待排序的序列的记录数目n较小，记录的关键字的排列基本有序，分布比较随机且对排序有稳定性要求时，宜选用插入排序。
4、当待排序的序列的记录数目n较小，并且对排序有稳定性要求进，宜选用选择排序；若记录的关键字的值不接近逆序，也可选用直接插入排序。
19
内部算法性能分析 第1章 前 言
第5章 排序算法的改进
5.1双向冒泡排序算法
对于输入的子序列 L [ low…High ]看成竖着排列的“气泡”,然后分别从上端 (Low)向底端 ( High)扫描。在扫描的过程中时刻注意两个相邻元素的顺序 ,保证上端的元素小于下端的元素 ,这样经过一趟扫描后就使较大的元素沉到下面。然后再从底端向上端扫描 ,由于在前一趟扫描过程中最大的元素已经沉到最底端 ,所以这次扫描最大的元素不再参加排序 ,将剩下的元素进行排序 ,排序的过程中保证使得底端元素大于顶端元素。这样反复的扫描 ,并不断缩小排序空间 ,直到整个序列有序位置。这样直观上看 ,双向冒泡排序法先让重的气泡沉到底下 ,然后让轻的气泡浮上来 ,然后再让大的气泡沉下去 ,让次轻的气泡浮上来 ,依次反复 ,直到带排序列有序为止。
算法是利用两个指针 low和 high记录带排序列区域 L [ low…high ] ,用指针变量 t记录在每趟扫描过程中最近一次交换记录的位置 ,在每次扫描开始 t的初始值分别为 Low或 high ,并且在扫描结束后再让 t和 low或 high进行比较 ,如果发现某次 t值没有改变 ,则说明序列已经有序 ,并且用 break跳出循环 ,提前结束排序。 代码实现：
While (low < high)
{
t=low;//t指向带排序区间的离最底端
For (i = low ; i < high ; i + + )
{
if (L [ i ] > L [ i + 1 ] )
{m=l[i];l[i]=l[i+1];l[i+1]=m;
t=i;} //记录最近一次移动的关键字的位置 if(t==low) break; //检查是否待排关键字有序，如有序则退出循环，结束排序
else high=t; //缩小待排序列的范围 for (i = high ; i > low ; i + + ) { if (L[ i ] < L [ i - 1 ])
m=l[i];l[i]=l[i+1];l[i+1]=m;t=i;} //记录最近一次移动的关键字的位置
If(t==high) break; //检查是否排关键字有序，如有序则退出循环，
结束排序
20
内部算法性能分析 第5章 排序算法的改进
else low=t; ｝ //缩小待排序列的范围
算法分析：双向冒泡排算法是原地置换算法，并且由于 L [ i ]〉L [ i + 1 ]或者 L [ i ] < L [ i - 1 ]时才进行交换，所以说该算法也是稳定的排序方法，但如果改为 L [ i ]〉= L [ i + 1 ]或者 L [ i ] < = L [ i - 1 ]时才进行交换 , 则改变其的稳定性。该算法在执行一趟排序后同时确定两个记录的位置 ,即待排区域的最大和最小的记录，而书中提到的冒泡排序在执行行一趟排序后仅能确定一个记录的位置，即最大或最小的，显然该算法更可取。
5.2双倍快速排序的算法
快速排序的基本思想是基于分支策略的思想。即对于输入的子序列 L [ low…High ] ,如果规模足够小则直接进行排序 ,否则分三步处理 :
分解 (Divide) :设输入的序列 L [ low…High ] ,确定支点元素 L [ low ]和 L [ High ] ,并使 L [Low ] . key < = Ll[ High ] . key ,然后分解 (Divide) :将序列 L [ low…High ]划分成三个子序列 L [Low. . L - 1 ]、[L + 1. . H -1 ]和 L [ H + 1. . High ] ,使 L [ low…High ]中元素的关系为 L [Low. . L - 1 ] < L [L ] < L [L + 1. . H - 1 ] < L[ H] < L [ H + 1. . High ]。
递归求解 (Conquer) :通过递归调用快速排序算法分别对 L [Low. . L - 1 ]、[L + 1. . H - 1 ]和 L [ H + 1. .High ]分别进行分解排序。
合并 (Merge) :由于对分解出的三个子序列的排序是就地进行的 ,所以在 L [Low. . L - 1 ]、[L + 1. . H- 1 ]和 L [ H + 1. . High ]都排好序后不需要执行任何计算 L [ low…High ]就已排好序。
算法描述：
该算法首先用QSort对序的L [ low…high ]区间进行分解 ,把此序列区间分解为五部分 ,其中 L [L ]和L[H]是两个分界点，并从这两个分界点处将整个序列分解为三个部分，分别为L [ low… - 1 ]、[L + 1…H-1]、[ H + 1…high ] ,然后再递归调用 QSort分别对三个序列进行分解 ,这样直到递归到最后 ,L [ low…high ]便成为一个有序的序列。然后再对给定序列 L [ 1…L. lengh ]进行快速排 QuickSort ( Sqlist &L) )时即直接调用QSort即可。
算法实现： n=high-low; if(r[row]>r[high])
{
t=r[row]; //确保区间内第一个元素的值不大于区间内最后一个元素的值 r[row]=r[high];r[high]=t;
l=low; //小于区间内第一个元素的值数组边界下标
21