查找与排序-插入排序

思考：在把待排序的元素插入已经有序的子序列中时，是不是一定要逐一比较？有没有改进方法？

在查找插入位置的时候可以采用折半（二分）搜索的办法。

一、折半插入排序

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 = 0high = i - 1temp =self.data[i]while low <= high:mid = (low + high) // 2if temp < self.data[mid]:high = mid - 1else:low = mid + 1j = i - 1while j >= low:self.data[j + 1] = self.data[j]j = j - 1self.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_lenwhile True:gap = gap // 3 + 1      # 保证增量递减且最后为1for i in range(gap, data_len):temp = Record(self.data[i].key, self.data[i].value)j = i-gapwhile j >= 0 and temp.key < self.data[j].key:self.data[j+gap].key = self.data[j].keyj = j-gapself.data[j + gap] = tempif gap == 1:break

4.希尔排序算法分析

（1）空间复杂度：也需要一个数据元素空间，其空间复杂度为O(1)。      

（2）时间复杂度：希尔排序的时间复杂度分析是个非常复杂的问题，因为其性能与所选增量序列有关（介于O(n)和O(n2)之间）。      

（3）希尔排序算法是不稳定算法。