给定一个初始有序数组 [2, 5, 8, 12, 15],使用折半插入排序算法插入新元素 10。请问在插入过程中,元素 12 被移动了几次?
答案解析
核心考点说明:本题考察折半插入排序的插入过程,特别是元素移动的次数。
解题思路分析:折半插入排序先使用折半查找确定新元素插入的位置,然后将插入位置后的元素依次后移。我们需要模拟整个插入过程来计算元素12的移动次数。
每个选项的详细分析:
A. 0次:这是错误的。10需要插入到8和12之间,这会导致12移动。
B. 1次:这是正确的。插入位置通过二分查找确定在8之后,需要将包括12在内的后面元素向后移动一位,12只移动一次。
C. 2次:这是错误的。虽然排序可能会有多次移动,但12这个元素只会因为10的插入而移动一次。
D. 3次:这是错误的。 10的插入只会导致12移动一次,不会移动3次。
易错点提醒:容易忽略折半插入排序的移动特性,认为多次移动某个元素。
详细步骤:
1. 初始数组:[2, 5, 8, 12, 15]
2. 折半查找确定10的插入位置:10应该插入到8和12之间。
3. 为了给10腾出位置,需要将 12 和 15 向后移动一位,变成 [2, 5, 8, _, 12, 15]
4. 最终插入: [2, 5, 8, 10, 12, 15]。12移动了一次。
正确答案的关键依据:折半插入排序的移动过程。
错误选项的具体问题:选项A认为不需要移动,而选项C和D夸大了移动次数。
正确答案:B