如果原序列是降序,而最终结果应该是升 序,故每一轮中待插入元素要和所有已排好 序的元素进行比较(包括哨兵在内),而且 这些元素都要依次后移(哨兵不后移),以 便将首元位置空出,让待插元素插到最前面 的位置。这样, 比较次数为 Compare=2+3+.+N=(N+2)大(N-1)/2 移动次数为: shift 1+2+…+(N-1)=N大(N-1)/2 所以标准操作次数: +① compare shift O(N2)
如果原序列是降序，而最终结果应该是升 序，故每一轮中待插入元素要和所有已排好 序的元素进行比较（包括哨兵在内），而且 这些元素都要依次后移（哨兵不后移），以 便将首元位置空出，让待插元素插到最前面 的位置。这样， 比较次数为： Tcompare =2+3+…+N=(N+2)*(N-1)/2 移动次数为： Tshift =1+2+…+(N-1)=N*(N-1)/2 所以标准操作次数： Tmax=Tcompare+Tshift=O(N2)
注意 上面计算移动记录次数的过程中,并没有 考虑以下两个赋值操作:给哨兵赋值的操作和 将待插元素插到正确位置的赋值操作 如果将这两项计算在内,那么移动次数都 应再加上2(N-1)的值。考虑到排序序列中各 元素值是随机取值的,所以它们之间大小排列 也是随机的,因此各种排列概率相同,我们取 最差时间效率与最好时间效率的平均值做为直 接插入排序的平均时间复杂度,为o(Nx2)。在 算法中我们多开了一个辅助空间,故空间复杂 度为O(1)
注意： 上面计算移动记录次数的过程中，并没有 考虑以下两个赋值操作：给哨兵赋值的操作和 将待插元素插到正确位置的赋值操作。 如果将这两项计算在内，那么移动次数都 应再加上2(N-1)的值。考虑到排序序列中各 元素值是随机取值的，所以它们之间大小排列 也是随机的，因此各种排列概率相同，我们取 最差时间效率与最好时间效率的平均值做为直 接插入排序的平均时间复杂度，为O(N2)。在 算法中我们多开了一个辅助空间，故空间复杂 度为O(1)
822折半插入排序 在向有序表中插入元素的过程中, 直接插入排序采用的方法是:从后向前 依次与有序表中元素作比较。没有充分 利用“前部分已经有序”的特性,这种 方法效率较低
8.2.2 折半插入排序 在向有序表中插入元素的过程中， 直接插入排序采用的方法是：从后向前 依次与有序表中元素作比较。没有充分 利用“前部分已经有序”的特性，这种 方法效率较低
考虑改进的方法: 设定有序表长度为L,那么让待插元素x和 处于有序表中间位置的元素y作比较: 如果待插元素x大于或等于y,则说明插入 的位置一定在有序表的后半部分 如果待插元素x较小,则说明插入的位置 定在有序表的前半部分。 无论哪种情况,我们都可以将可能插入的 位置所在的空间长度降至原来长度的一半,故 称“折半”插入排序
考虑改进的方法： 设定有序表长度为L，那么让待插元素x和 处于有序表中间位置的元素y作比较： 如果待插元素x大于或等于y，则说明插入 的位置一定在有序表的后半部分； 如果待插元素x较小，则说明插入的位置 一定在有序表的前半部分。 无论哪种情况，我们都可以将可能插入的 位置所在的空间长度降至原来长度的一半，故 称“折半”插入排序
对于长度为工的有序表,大约需要 1og2L次的比较就可以确定出待插元素的 位置。因此对于N个元素的序列来说,进 行N-1轮的所有比较次数为O(N*1g2N), 显然优于直接插入法中平均情况下的比 较次数o(N2)。但是在确定了待插位置之 后,元素移动的次数并没有降下来,所 以时间复杂度仍为有O(N2)。 算法中仍旧多开了一个辅助空间 故空间复杂度为o(1),保持不变
对于长度为L的有序表，大约需要 log2L次的比较就可以确定出待插元素的 位置。因此对于N个元素的序列来说，进 行N-1轮的所有比较次数为O(N*log2N)， 显然优于直接插入法中平均情况下的比 较次数O(N2)。但是在确定了待插位置之 后，元素移动的次数并没有降下来，所 以时间复杂度仍为有O(N2)。 算法中仍旧多开了一个辅助空间， 故空间复杂度为O(1)，保持不变