课后作业部分第九章查找
序. 起泡排序. 快速排序. 简单选择排序以及二路归并排序每趟的结果。
2. 判别下列序列是否为堆，如不是，按照堆排序思想把它调整为堆，用图表示建堆的过程。
⑴（1，5，7，25，21，8，8，42） ⑵（3，9，5，8，4，17，21，6）
【解答】序列⑴是堆，序列⑵不是堆，调整为堆（假设为大根堆）的过程如下图所示。
24
课后作业部分第九章查找
四. 算法设计
1. 直接插入排序中寻找插入位置的操作可以通过折半查找来实现。据此写一个改进的插入排序的算法。
#region 折半插入排序算法 void HalfInsertSort(int[] array) {
for(int i=2;i
array[0] = array[i]; //或者也可以添加if (array[i] < array[i - 1])先行判断 int low = 1; int high = i - 1; while(low <= high) {
int mid = (low + high) / 2;
if (array[0] < array[mid]) high = mid - 1; else low = mid + 1; } int j=0;
for (j = i - 1; j >= high + 1; --j) { array[j + 1] = array[j]; } array[j + 1] = array[0]; } }
#endregion
2. 已知（k1, k2, …, kn）是堆，试写一算法将（k1, k2, …, kn, kn+1）调整为堆
25