第十章 参考答案二、填空
1．稳定、不稳定 2.内部、外部
3．插入排序、交换排序、选择排序、归并排序 4.键值比较、记录移动、附加空间
5．直接、折半、表、希尔 6.2、r[j]、r[0]
7.O（n2）、O（1） 8.n-1、flag=1、n-i
9.O(n2) 10.j--、r[i]=r[j]、j++、r[j]=r[i]、x
11.O(nlog2n)、O(n2) 12.n-1、k=j、k!=I
13.O(n2) 14.n-1、存储区
15.叶子、树根、＋∝ 16.n-1、log2n、O(nlog2n)
17.完全二叉树、n/2 18.O(1)、O(nlog2n)
19.a[ii]、ii++、a[j]、j++、m、n、O(n-h+1) 20.有序
21．O(log2n) 22.O(n2)
23.冒泡排序、快速排序 24.插入排序、快速排序三、单项选择
1,③ 2,③ 3,② 4,② 5,② 6,②
7,③ 8,④ 9,① 10,③ 11,② 12,③
13,③ 14,④ 15,④ 16,③ 17,③ 18,②
19,④ 20,④ 21,④ 22,② 23,③
四、简答及应用
1．①直接插入排序序号 1 2 3 4 5 6 7 8 9 10 11 12
关键字 83 40 63 13 84 35 96 57 39 79 61 15
i = 2 40 83 [63 13 84 35 96 57 39 79 61 15]
i = 3 40 63 83 [13 84 35 96 57 39 79 61 15]
i = 4 13 40 63 83 [84 35 96 57 39 79 61 15]
i = 5 13 40 63 83 84 [35 96 57 39 79 61 15]
i = 6 13 35 40 63 83 84 [96 57 39 79 61 15]
i = 7 13 35 40 63 83 84 96 [57 39 79 61 15]
i = 8 13 35 40 57 63 83 84 96 [39 79 61 15]
i = 9 13 35 39 40 57 63 83 84 96 [79 61 15]
i = 10 13 35 39 40 57 63 79 83 84 96 [61 15]
i = 11 13 35 39 40 57 61 63 79 83 84 96 [15]
i = 12 13 15 35 39 40 57 61 63 79 83 84 96
②直接选择排序序号 1 2 3 4 5 6 7 8 9 10 11 12
关键字 83 40 63 13 84 35 96 57 39 79 61 15
i = 1 13 [40 63 83 84 35 96 57 39 79 61 15]
i = 2 13 15 [63 83 84 35 96 57 39 79 61 40]
i = 3 13 15 35 [83 84 63 96 57 39 79 61 40]
i = 4 13 15 35 39 [84 63 96 57 83 79 61 40]
i = 5 13 15 35 39 40 [63 96 57 83 79 61 84]
i = 6 13 15 35 39 40 57 [96 63 83 79 61 84]
i = 7 13 15 35 39 40 57 61 [63 83 79 96 84]
i = 8 13 15 35 39 40 57 61 63 [83 79 96 84]
i = 9 13 15 35 39 40 57 61 63 79 [83 96 84]
i = 10 13 15 35 39 40 57 61 63 79 83 [96 84]
i = 11 13 15 35 39 40 57 61 63 79 83 84 [96]
③快速排序
关键字 83 40 63 13 84 35 96 57 39 79 61 15
第一趟排序后 [15 40 63 13 61 35 79 57 39] 83 [96 84]
第二趟排序后 [13] 15 [63 40 61 35 79 57 39] 83 84 [96]
第三趟排序后 13 15 [39 40 61 35 57] 63 [79] 83 84 96
第四趟排序后 13 15 [35] 39 [61 40 57] 63 79 83 84 96
第五趟排序后 13 15 35 39 [57 40] 61 63 79 83 84 96
第六趟排序后 13 15 35 39 40 [57] 61 63 79 83 84 96
第七趟排序后 13 15 35 39 40 57 61 63 79 83 84 96
④堆排序关键字： 83 40 63 13 84 35 96 57 39 79 61 15
排序成功的序列：96 84 83 79 63 61 57 40 39 35 15 13
排序过程如图简答题8－1.1、8－1.2、8－1.3所示。
⑤归并排序
关键字 83 40 63 13 84 35 96 57 39 79 61 15
第一趟排序后 [40 83] [13 63] [35 84] [57 96] [39 79] [15 61]
第二趟排序后 [13 40 63 83] [35 57 84 96] [15 39 61 79]
第三趟排序后 [13 35 40 57 63 83 84 96] [15 39 61 79]
第四趟排序后 13 15 35 39 40 57 61 63 79 83 84 96
2．稳定排序有直接插入、冒泡排序、归并排序。
不稳定排序有快速排序、直接选择排序、堆排序。举例如下：
①快速排序初始状态 40 65 38 49 97 65 13 60
排序后 13 38 40 49 60 65 65 97
（65表示记录初始位置在65记录位置之后）
②堆排序初始状态 65 38 75 97 80 13 27 65
排序后 13 27 38 65 65 75 80 97
③直接排序初始状态 40 65 38 49 97 65 13 60
排序后 13 38 40 49 60 65 65 97
3．直接选择相对于树形选择排序的优点：算法易懂，容易实现，基本上不需要附加空间。而树形排序需要附加n – 1附加空间。
直接选择排序相对于树形选择排序的缺点：直接选择排序每一趟都不保留比较结果比较次数较多，而树形排序则能利用大部分上一次的比较结果，因此时间性能比直接选择排序优越。
堆排序相对于树形排序的优点：堆排序除建第一个堆费时外，其余元素进行堆比较次数小于等于h（h表示n元素构成的完全二叉树的深度），而树形排序每次比较都是h次。因此，堆排序时间复杂度小于树形排序。堆排序基本也不需要附加空间。
4．直接插入排序、直接选择排序、快速排序、堆排序和归并排序时空性如表：
平均时间
最坏情况
辅助空间
直接插入
O(n2)
O(n2)
O(n1)
直接选择
O(n2)
O(n2)
O(1)
快速排序
O(nlg2n)
O(n2)
O(nlog2n)
堆排序
O(nlog2n)
O(nlog2)
O(1)
归并排序
O(nlog2n)
O(nlog2n)
O(n)
从上表可以得出：就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下，时间性能不如堆排序和归并排序。 而后两者相比的结果是，当n较大时，归并排序所需时间优于堆排序，但它所需辅助空间最多。
注意，在所有排序方法中，没有哪一种是绝对最优的，有的适用于n较大的情况，有适用于n较小的情况，还有的与关键字的分布和初始位置有关……因此，在实际使用时，需要根据不同情况适当选用排序方法，甚至可将多种方法结合使用。
5．分析：先按序列画出对应的完全二叉树，再看其是否满足堆的定义。按这一思路，画出的完全二叉树见图简答8-5.1.
显然序列⑴是堆，而序列⑵不是堆，值为7的元素应该上调，调整过程见图简答题8-5.2.
6.第一趟,[46,58,15,45,90,18,10,62]
[46,58,15,45,90,18,10,62],
一次交换之后 [10,58,15,45,90,18,46,62]
二次交换之后 [10,46,15,45,90,18,58,62]
三次交换之后 [10,18,15,45,90,46,58,62]
[10,18,15,45,90,46,58,62]
[10,18,15,45,90,46,58,62]
四次交换之后 [10,18,15,45,46,90,58,62]
以上“－”表示当前经比较不交换位置的元素。“ ”表示当前经比较交换位置的元素。
第一趟： [10 18 15 45] 46 [90 58 62]
第二趟： 10 [18 15 45] 46 [62 58] 90
第三趟： 10 [15] 18 45] 46 [58] 62 90
结果,10 15 18 45 46 58 62 90
7．
⑴插入排序的每趟的结果
初始值健值序列 [12] 5 9 20 6 31 24
i=2 [5 12] 9 20 6 31 24
i=3 [5 9 12] 20 6 31 24
i=4 [5 9 12 20] 6 31 24
i=5 [5 6 9 12 20] 31 24
i=6 [5 6 9 12 20 31] 24
i=7 [5 6 9 12 20 24 31]
⑵冒泡排序的每趟的结果：
初始键值序列 [12 5 9 20 6 31 24]
第一趟之后 [5 9 12 6 20 24] 31
第二趟之后 [5 9 6 12 20] 24 31
第三趟之后 [5 6 9 12] 20 24 31
第四趟之后 5 6 9 12 20 24 31
五、算法设计
1.分析：每趟从单链表头部开始，顺序查找当前链值最小的结点。找到后，插入到当前的有序表区的最后。
Void selesort ( lklist L ) /* 设链表L带头结点 */
{ q=L; /* 指向第一数据前趋 */
while ( q-> next !=NULL )
{ pl = q -> next ;
minp =pl; /* minp指向当前已知的最小数 */
while ( pl -> next != NULL )
{ if ( pl -> next -> data < minp -> data )
minp = pl -> next ; /* 找到了更小数 */
pl = pl -> next ; /* 继续往下找 */
}
if ( minp != q -> next) /* 将最小数交换到第一个位置上 */
{ r1 = minp -> next ;
minp -> next = r1 -> next ; /* 删除最小数 */
r2 = q -> next ;
q -> next = r2 -> next ; /* 删除当前表中第一个数 */
r1 -> next = q -> next ;
q -> next = r1 ; /* 将最小数插入到第一个位置上 */
r2 -> next = minp -> next ;
minp -> next = r2 ; /* 将原第一个数放到最小数原位置上 */
}
q = q > next ; /* 选择下一个最小数 */
}
}
2.分析：先调用划分函数 quickpass (),以确定中间元素的位置，然后再借助栈分别对中间元素左、右两边的区域进行快速排序。
Void qksort ( list A ) /* n为元素个数 */
{ InitStack ( S ) ; /* 设置一个栈保存有关参数和变量 */
j = 1 ; h = n ; /* j,h 分别指向表头和表尾 */
while ( ( j < h ) ‖( !empty ( S ) ) )
{ while ( j < h )
{ quickpass ( A,j,h,i ) ; /* 划分函数 quickpass () 参照教材 */
push ( S,j,h,i ) ; /* 保存变量值 */
h = i – 1 ; /* 设置对左边进行划分的参数 */
}
if ( !empty ( S ) )
{ pop ( S,j,h,i ) ; /* 取出变量值 */
j = i + 1 ; /* 设置对右边进行划分的参数 */
}
}
}
3．分析：插入排序的基本思想是：每趟从无序区间中取出一个元素，再按键值大小插入到前面的有序区间中。对于有序区，当然可以用二分查找来确定插入位置。
Void straightsort ( list A ) /* n为元素个数，数组下标从1开始，到n结束。 */
{ for ( i =2 ; i <= n ; i + + )
{ low = 1 ; high = i – 1 ; /* low,high 分为当前元素上、下界 */
A[0],key = A[i],key ;
While ( low <= high )
{ mid = ( low + high ) /2 ;
switch
{ case,A[0],key <= A[mid],key,high = mid – 1 ; /* 修改上界 */
case,A[0],key > A[mid],key,low = mid + 1 ; /* 修改下界 */
}
for ( j = i-1 ; j >= mid ; j - -) A [j +1] = A [ j ] ; /* 移动数据 */
A[ mid ] = A[ i ] ;
}
}
}
4．分析：本题的算法思想是：先设置好上、下界，然后分别从线性表两端查找正数和负数，找到后进行交换，直到上、下界相遇。
Void example ( datatype A [n] )
{ i = 1,j = n ; /* i,j为左右边界 */
while ( i < j )
{ while ( ( i < j ) && ( A[ i ] < 0 ) ) i++ ; /* 在左边界找正数 */
while ( (i < j ) && ( A[ j ] > 0 )) j - - ; /* 在右边界找负数 */
if ( i < j)
{ temp = A[ i ]; A[ i ] = A[ j ]; A[ j ] = A [temp ] ; /*交换两个元素的值 */
i++ ; j - -;
}
}
}
5．分析：此问题分为两个算法，第一个算法 shift 假设 a[ 1],a[ 2 ],…,a[ k]为堆，增加一个无素a[ k + 1 ],把数组a[ 1 ],a[ 2 ],…,a[ k + 1 ]调整为堆。第二个算法heep 从1开始调用算法sift将整个数组调整为堆。
Void sift (datatype A[ n ],int K) /* n > = k + 1 */
{ x = A[ K+1] ;
i = K +1 ;
while ( ( i/2 > 0 )&&( A[i/2]>x) ) { A[i]= A[i./2]; i = i/2;} /*从下往上插入位置 */
A[i] = x ;
}
Void heap ( datatype A[ n ] ) ; /* 从1开始调用算法sift,将整个数组调整为堆 */
{ for ( k = 1 ; k <= n-1; k++ ) sift ( A,k ) ; }
6．分析：本算法采用的存储结构是带头结点的双循环链表。首先找元素插入位置，然后把元素从原链表中删除，插入到相应的位置处。请注意双链表上插入和删除操作的步骤。
Void sort ( dlklist H ) /* 链表H采用带头结点的双循环链表 */
{ pre = H -> next ;
while ( p != H )
{p = pre -> next ; /* p是有序表的末尾 */
q = p -> next ; /* 保存下一个插入元素 */
while((pre!=H)&&(p->data<pre ->data))pre=pre–prior; /*从后往前找插入位置 */
if ( pre ! =p -> prior )
{ p-> prior->next = p -> next ; /* 删除p */
p-> next->prior = p -> prior;
p->next = pre ->next ; /* 插入到pre之后 */
pre -> next -> prior = p ;
p ->prior= pre ; pre ->next = p ;
}
p=q;
}
}
1．稳定、不稳定 2.内部、外部
3．插入排序、交换排序、选择排序、归并排序 4.键值比较、记录移动、附加空间
5．直接、折半、表、希尔 6.2、r[j]、r[0]
7.O（n2）、O（1） 8.n-1、flag=1、n-i
9.O(n2) 10.j--、r[i]=r[j]、j++、r[j]=r[i]、x
11.O(nlog2n)、O(n2) 12.n-1、k=j、k!=I
13.O(n2) 14.n-1、存储区
15.叶子、树根、＋∝ 16.n-1、log2n、O(nlog2n)
17.完全二叉树、n/2 18.O(1)、O(nlog2n)
19.a[ii]、ii++、a[j]、j++、m、n、O(n-h+1) 20.有序
21．O(log2n) 22.O(n2)
23.冒泡排序、快速排序 24.插入排序、快速排序三、单项选择
1,③ 2,③ 3,② 4,② 5,② 6,②
7,③ 8,④ 9,① 10,③ 11,② 12,③
13,③ 14,④ 15,④ 16,③ 17,③ 18,②
19,④ 20,④ 21,④ 22,② 23,③
四、简答及应用
1．①直接插入排序序号 1 2 3 4 5 6 7 8 9 10 11 12
关键字 83 40 63 13 84 35 96 57 39 79 61 15
i = 2 40 83 [63 13 84 35 96 57 39 79 61 15]
i = 3 40 63 83 [13 84 35 96 57 39 79 61 15]
i = 4 13 40 63 83 [84 35 96 57 39 79 61 15]
i = 5 13 40 63 83 84 [35 96 57 39 79 61 15]
i = 6 13 35 40 63 83 84 [96 57 39 79 61 15]
i = 7 13 35 40 63 83 84 96 [57 39 79 61 15]
i = 8 13 35 40 57 63 83 84 96 [39 79 61 15]
i = 9 13 35 39 40 57 63 83 84 96 [79 61 15]
i = 10 13 35 39 40 57 63 79 83 84 96 [61 15]
i = 11 13 35 39 40 57 61 63 79 83 84 96 [15]
i = 12 13 15 35 39 40 57 61 63 79 83 84 96
②直接选择排序序号 1 2 3 4 5 6 7 8 9 10 11 12
关键字 83 40 63 13 84 35 96 57 39 79 61 15
i = 1 13 [40 63 83 84 35 96 57 39 79 61 15]
i = 2 13 15 [63 83 84 35 96 57 39 79 61 40]
i = 3 13 15 35 [83 84 63 96 57 39 79 61 40]
i = 4 13 15 35 39 [84 63 96 57 83 79 61 40]
i = 5 13 15 35 39 40 [63 96 57 83 79 61 84]
i = 6 13 15 35 39 40 57 [96 63 83 79 61 84]
i = 7 13 15 35 39 40 57 61 [63 83 79 96 84]
i = 8 13 15 35 39 40 57 61 63 [83 79 96 84]
i = 9 13 15 35 39 40 57 61 63 79 [83 96 84]
i = 10 13 15 35 39 40 57 61 63 79 83 [96 84]
i = 11 13 15 35 39 40 57 61 63 79 83 84 [96]
③快速排序
关键字 83 40 63 13 84 35 96 57 39 79 61 15
第一趟排序后 [15 40 63 13 61 35 79 57 39] 83 [96 84]
第二趟排序后 [13] 15 [63 40 61 35 79 57 39] 83 84 [96]
第三趟排序后 13 15 [39 40 61 35 57] 63 [79] 83 84 96
第四趟排序后 13 15 [35] 39 [61 40 57] 63 79 83 84 96
第五趟排序后 13 15 35 39 [57 40] 61 63 79 83 84 96
第六趟排序后 13 15 35 39 40 [57] 61 63 79 83 84 96
第七趟排序后 13 15 35 39 40 57 61 63 79 83 84 96
④堆排序关键字： 83 40 63 13 84 35 96 57 39 79 61 15
排序成功的序列：96 84 83 79 63 61 57 40 39 35 15 13
排序过程如图简答题8－1.1、8－1.2、8－1.3所示。
⑤归并排序
关键字 83 40 63 13 84 35 96 57 39 79 61 15
第一趟排序后 [40 83] [13 63] [35 84] [57 96] [39 79] [15 61]
第二趟排序后 [13 40 63 83] [35 57 84 96] [15 39 61 79]
第三趟排序后 [13 35 40 57 63 83 84 96] [15 39 61 79]
第四趟排序后 13 15 35 39 40 57 61 63 79 83 84 96
2．稳定排序有直接插入、冒泡排序、归并排序。
不稳定排序有快速排序、直接选择排序、堆排序。举例如下：
①快速排序初始状态 40 65 38 49 97 65 13 60
排序后 13 38 40 49 60 65 65 97
（65表示记录初始位置在65记录位置之后）
②堆排序初始状态 65 38 75 97 80 13 27 65
排序后 13 27 38 65 65 75 80 97
③直接排序初始状态 40 65 38 49 97 65 13 60
排序后 13 38 40 49 60 65 65 97
3．直接选择相对于树形选择排序的优点：算法易懂，容易实现，基本上不需要附加空间。而树形排序需要附加n – 1附加空间。
直接选择排序相对于树形选择排序的缺点：直接选择排序每一趟都不保留比较结果比较次数较多，而树形排序则能利用大部分上一次的比较结果，因此时间性能比直接选择排序优越。
堆排序相对于树形排序的优点：堆排序除建第一个堆费时外，其余元素进行堆比较次数小于等于h（h表示n元素构成的完全二叉树的深度），而树形排序每次比较都是h次。因此，堆排序时间复杂度小于树形排序。堆排序基本也不需要附加空间。
4．直接插入排序、直接选择排序、快速排序、堆排序和归并排序时空性如表：
平均时间
最坏情况
辅助空间
直接插入
O(n2)
O(n2)
O(n1)
直接选择
O(n2)
O(n2)
O(1)
快速排序
O(nlg2n)
O(n2)
O(nlog2n)
堆排序
O(nlog2n)
O(nlog2)
O(1)
归并排序
O(nlog2n)
O(nlog2n)
O(n)
从上表可以得出：就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下，时间性能不如堆排序和归并排序。 而后两者相比的结果是，当n较大时，归并排序所需时间优于堆排序，但它所需辅助空间最多。
注意，在所有排序方法中，没有哪一种是绝对最优的，有的适用于n较大的情况，有适用于n较小的情况，还有的与关键字的分布和初始位置有关……因此，在实际使用时，需要根据不同情况适当选用排序方法，甚至可将多种方法结合使用。
5．分析：先按序列画出对应的完全二叉树，再看其是否满足堆的定义。按这一思路，画出的完全二叉树见图简答8-5.1.
显然序列⑴是堆，而序列⑵不是堆，值为7的元素应该上调，调整过程见图简答题8-5.2.
6.第一趟,[46,58,15,45,90,18,10,62]
[46,58,15,45,90,18,10,62],
一次交换之后 [10,58,15,45,90,18,46,62]
二次交换之后 [10,46,15,45,90,18,58,62]
三次交换之后 [10,18,15,45,90,46,58,62]
[10,18,15,45,90,46,58,62]
[10,18,15,45,90,46,58,62]
四次交换之后 [10,18,15,45,46,90,58,62]
以上“－”表示当前经比较不交换位置的元素。“ ”表示当前经比较交换位置的元素。
第一趟： [10 18 15 45] 46 [90 58 62]
第二趟： 10 [18 15 45] 46 [62 58] 90
第三趟： 10 [15] 18 45] 46 [58] 62 90
结果,10 15 18 45 46 58 62 90
7．
⑴插入排序的每趟的结果
初始值健值序列 [12] 5 9 20 6 31 24
i=2 [5 12] 9 20 6 31 24
i=3 [5 9 12] 20 6 31 24
i=4 [5 9 12 20] 6 31 24
i=5 [5 6 9 12 20] 31 24
i=6 [5 6 9 12 20 31] 24
i=7 [5 6 9 12 20 24 31]
⑵冒泡排序的每趟的结果：
初始键值序列 [12 5 9 20 6 31 24]
第一趟之后 [5 9 12 6 20 24] 31
第二趟之后 [5 9 6 12 20] 24 31
第三趟之后 [5 6 9 12] 20 24 31
第四趟之后 5 6 9 12 20 24 31
五、算法设计
1.分析：每趟从单链表头部开始，顺序查找当前链值最小的结点。找到后，插入到当前的有序表区的最后。
Void selesort ( lklist L ) /* 设链表L带头结点 */
{ q=L; /* 指向第一数据前趋 */
while ( q-> next !=NULL )
{ pl = q -> next ;
minp =pl; /* minp指向当前已知的最小数 */
while ( pl -> next != NULL )
{ if ( pl -> next -> data < minp -> data )
minp = pl -> next ; /* 找到了更小数 */
pl = pl -> next ; /* 继续往下找 */
}
if ( minp != q -> next) /* 将最小数交换到第一个位置上 */
{ r1 = minp -> next ;
minp -> next = r1 -> next ; /* 删除最小数 */
r2 = q -> next ;
q -> next = r2 -> next ; /* 删除当前表中第一个数 */
r1 -> next = q -> next ;
q -> next = r1 ; /* 将最小数插入到第一个位置上 */
r2 -> next = minp -> next ;
minp -> next = r2 ; /* 将原第一个数放到最小数原位置上 */
}
q = q > next ; /* 选择下一个最小数 */
}
}
2.分析：先调用划分函数 quickpass (),以确定中间元素的位置，然后再借助栈分别对中间元素左、右两边的区域进行快速排序。
Void qksort ( list A ) /* n为元素个数 */
{ InitStack ( S ) ; /* 设置一个栈保存有关参数和变量 */
j = 1 ; h = n ; /* j,h 分别指向表头和表尾 */
while ( ( j < h ) ‖( !empty ( S ) ) )
{ while ( j < h )
{ quickpass ( A,j,h,i ) ; /* 划分函数 quickpass () 参照教材 */
push ( S,j,h,i ) ; /* 保存变量值 */
h = i – 1 ; /* 设置对左边进行划分的参数 */
}
if ( !empty ( S ) )
{ pop ( S,j,h,i ) ; /* 取出变量值 */
j = i + 1 ; /* 设置对右边进行划分的参数 */
}
}
}
3．分析：插入排序的基本思想是：每趟从无序区间中取出一个元素，再按键值大小插入到前面的有序区间中。对于有序区，当然可以用二分查找来确定插入位置。
Void straightsort ( list A ) /* n为元素个数，数组下标从1开始，到n结束。 */
{ for ( i =2 ; i <= n ; i + + )
{ low = 1 ; high = i – 1 ; /* low,high 分为当前元素上、下界 */
A[0],key = A[i],key ;
While ( low <= high )
{ mid = ( low + high ) /2 ;
switch
{ case,A[0],key <= A[mid],key,high = mid – 1 ; /* 修改上界 */
case,A[0],key > A[mid],key,low = mid + 1 ; /* 修改下界 */
}
for ( j = i-1 ; j >= mid ; j - -) A [j +1] = A [ j ] ; /* 移动数据 */
A[ mid ] = A[ i ] ;
}
}
}
4．分析：本题的算法思想是：先设置好上、下界，然后分别从线性表两端查找正数和负数，找到后进行交换，直到上、下界相遇。
Void example ( datatype A [n] )
{ i = 1,j = n ; /* i,j为左右边界 */
while ( i < j )
{ while ( ( i < j ) && ( A[ i ] < 0 ) ) i++ ; /* 在左边界找正数 */
while ( (i < j ) && ( A[ j ] > 0 )) j - - ; /* 在右边界找负数 */
if ( i < j)
{ temp = A[ i ]; A[ i ] = A[ j ]; A[ j ] = A [temp ] ; /*交换两个元素的值 */
i++ ; j - -;
}
}
}
5．分析：此问题分为两个算法，第一个算法 shift 假设 a[ 1],a[ 2 ],…,a[ k]为堆，增加一个无素a[ k + 1 ],把数组a[ 1 ],a[ 2 ],…,a[ k + 1 ]调整为堆。第二个算法heep 从1开始调用算法sift将整个数组调整为堆。
Void sift (datatype A[ n ],int K) /* n > = k + 1 */
{ x = A[ K+1] ;
i = K +1 ;
while ( ( i/2 > 0 )&&( A[i/2]>x) ) { A[i]= A[i./2]; i = i/2;} /*从下往上插入位置 */
A[i] = x ;
}
Void heap ( datatype A[ n ] ) ; /* 从1开始调用算法sift,将整个数组调整为堆 */
{ for ( k = 1 ; k <= n-1; k++ ) sift ( A,k ) ; }
6．分析：本算法采用的存储结构是带头结点的双循环链表。首先找元素插入位置，然后把元素从原链表中删除，插入到相应的位置处。请注意双链表上插入和删除操作的步骤。
Void sort ( dlklist H ) /* 链表H采用带头结点的双循环链表 */
{ pre = H -> next ;
while ( p != H )
{p = pre -> next ; /* p是有序表的末尾 */
q = p -> next ; /* 保存下一个插入元素 */
while((pre!=H)&&(p->data<pre ->data))pre=pre–prior; /*从后往前找插入位置 */
if ( pre ! =p -> prior )
{ p-> prior->next = p -> next ; /* 删除p */
p-> next->prior = p -> prior;
p->next = pre ->next ; /* 插入到pre之后 */
pre -> next -> prior = p ;
p ->prior= pre ; pre ->next = p ;
}
p=q;
}
}
