思考：在把待排序的元素插入已经有序的子序列中时，是不是一定要逐一比较？有没有改进方法？
在查找插入位置的时候可以采用折半（二分）搜索的办法。
一、折半插入排序
1.折半插入排序算法的基本思想
假设待排序的n个数据元素存放在数组a中，那么折半插入排序可做如下描述：
（1）初始条件，有序子序列中只有一个元素a[0]；
（2）从a[1]开始，对于每次要插入的数据元素a[i]，使用折半查找法，查找a[i] 在已经有序的序列中的插入位置，然后进行插入。
（3）循环n-1次，直到所有元素都插入到有序序列中，算法结束。
2.折半插入排序代码
def bin_insertion_sort(self):
data_len = len(self.data)
for i in range(1, data_len):
if self.data[i] < self.data[i - 1]:
low = 0
high = i - 1
temp =self.data[i]
while low <= high:
mid = (low + high) // 2
if temp < self.data[mid]:
high = mid - 1
else:
low = mid + 1
j = i - 1
while j >= low:
self.data[j + 1] = self.data[j]
j = j - 1
self.data[low] = temp
3.折半插入排序举例
例：设待排元素序列为{16，15，19，16，18，19，20，14}，请给出折半插入排序算法按关键字递增排列。
4.折半插入排序算法分析
（1）空间复杂度：折半插入排序与直接插入排序一样，空间上只需要一个记录大小的辅助空间来临时存放待插入记录，空间复杂度为O(1)。
（2）时间复杂度：折半插入排序这种改进考虑了数据元素的比较次数。要插入a[i]时，要在长度为i的有序序列中查找位置，因此综合起来，总的比较次数nlog2n。但是折半插入排序并没有减少数据元素移动的次数，因此，其时间复杂度仍然是O(n2)。
（3）其他方面：折半查找只能用于顺序结构存储的序列，当初始记录无序性强，数据元素个数较多时效率较高，是一种稳定的排序方法。
二、希尔排序
1.希尔算法的基本思想
（1）把数据元素按照增量分为若干个小组，对每个小组内元素利用直接插入排序进行排序。 （2）通过分组，使得每次利用直接插入排序的元素个数降低；
（3）通过每次组内排序，使得整个序列趋向于有序。
（4）每趟排序过后，再按照新的更小的增量进行上述过程，直至增量为1，所有数据元素都在一个小组内排序后算法结束。
2.希尔排序举例
例：设待排元素序列为{56,25,70,99,82,10,15,56,42,18 }，取增量序列为{5，3，1}，请给出希尔排序法进行排序的过程。
3.希尔排序代码
def shell_sort(self):
data_len = len(self.data)
gap = data_len
while True:
gap = gap // 3 + 1 # 保证增量递减且最后为1
for i in range(gap, data_len):
temp = Record(self.data[i].key, self.data[i].value)
j = i-gap
while j >= 0 and temp.key < self.data[j].key:
self.data[j+gap].key = self.data[j].key
j = j-gap
self.data[j + gap] = temp
if gap == 1:
break
4.希尔排序算法分析
（1）空间复杂度：也需要一个数据元素空间，其空间复杂度为O(1)。
（2）时间复杂度：希尔排序的时间复杂度分析是个非常复杂的问题，因为其性能与所选增量序列有关（介于O(n)和O(n2)之间）。
（3）希尔排序算法是不稳定算法。