你可能喜欢
问答题
已知下列各种初始状态(长度为n)的元素,试问当利用直接插入排序进行排序时,至少需要进行多少次比较(要求排序后的记录由小到大顺序排列)?
⑴关键码从小到大有序(key1< key2< …< keyn)。
⑵关键码从大到小有序(key1> key2 >…> keyn)。
⑶奇数关键码顺序有序,偶数关键码顺序有序(key1< key3< …,key2key4…)。
⑷前半部分元素按关键码顺序有序,后半部分元素按关键码顺序有序,即:(key1< key2< …< keym,keym+1<
keym+2 <…)
问答题
判别下列序列是否为堆,如不是,按照堆排序思想把它调整为堆,用图表示建堆的过程。
⑴(1,5,7,25,21,8,8,42)
⑵(3,9,5,8,4,17,21,6)
序列⑴是堆,序列⑵不是堆,调整为堆(假设为大根堆)的过程如下图所示。
问答题
用上述排序方法的每趟结果如下: