插入排序

前言

插入排序的思想很直观，其在性能上不如一些分治的排序策略，例如快速排序，归并排序。插入排序是一种基于比较的排序算法。

算法思想

其类似于打牌的抓牌环节，抓到牌后都会按照点数插入到合适的位置，核心思想是保证一个已排序区间，剩下的未排序区间依次与前面的已排序区间进行比较，插入到对应的位置。

插入

有关于插入，若是序列是使用数组进行存储，则可以从右向左扫描已排序数组，因为这样可以在性能上有所优化。因为对于数组的插入，其不像链表一样，只需要断链，然后链接，其需要移动大量的元素，才能够进行插入，若是从左向右，譬如数组的长度为n，在位置i插入，则需要扫描i次，然后移动n-i+1次，最后插入数据。若是从右向左，最多需要i次扫描，然后可以边扫描边右移动

基本插入算法

复杂度:O(n^2)
比较次数（查找）: O(n^2)

移动次数（插入后导致的移动）: O(n^2)

def insertSort(arraylist):
  arrayLen = len(arraylist)
  for i in range(1, arrayLen):
      current = arraylist[i]
      j = i - 1
      while j > 0 and arraylist[j] < current:
          arraylist[j+1] = arraylist[j]
          j = j - 1
      arraylist[j+1] = current
  return arraylist

优化一：使用鶸二分查找

因为已经确定了前面的排序区间是有序的，所以可以直接使用二分查找来确定插入的位置，这样查找的时间就得到了优化

复杂度: O(n^2)
比较次数: O(nlgn)

移动次数: O(n^2)
```python
def binarySearch(arraylist, key):
low = 0
high = len(arraylist)
while low < high:

  mid = (log + hig)//2
  if arraylist[mid] == key:
      return mid
  elif arraylist[mid] > key:
      high = mid
  else:
      low = mid + 1

return low

def insertSort(arraylist):
arrayLen = len(arraylist)
for i in range(1, arrayLen):
current = arraylist[i]
position = binarySearch(arraylist[:i], key)
for i in range(i, position, -1):
arraylist[i] = arraylist[i-1]
arraylist[position] = current
return arraylist


## 优化二： 为了优化而优化的链表
使用链表之后，改变其数据结构，可以优化插入的时间，由最初的O(n)优化到了O(1)
+ 复杂度: O(n^2)
+ 比较次数: O(n^2)
+ 移动次数: O(1)
```python
def insert(arrayList, next, i):
    j = -1
    # print("当前j为{}, next[j]={}，arrayList[next[j]]={} arrayList[i]={}".format(j, next[j], arrayList[next[j]], arrayList[i]))
    while next[j] != -1 and arrayList[next[j]] < arrayList[i]:
        j = next[j]
        # print("目前j={}".format(j))
    next[j], next[i] = i, next[j]
    # print("交换后的next[j]={}, next[i]={} \n".format(next[j], next[i]))


def reorder(arrayList, next):
    i = -1
    ys = []
    while next[i] != -1:
        ys.append(arrayList[next[i]])
        i = next[i]
    return ys


def insertSortIII(arrayList):
    arrayLen = len(arrayList)
    next = [-1]*(arrayLen+1)
    for i in range(arrayLen):
        insert(arrayList, next, i)
    return reorder(arrayList, next)

优化三：终极进化之二叉搜索树

对于以上的优化，只能在插入和查找之中二选一的进行优化。单独提高其中一个仍会使插入算法保持在O(n^2)中，使用二分查找能够将查找次数降到最低—-O(lgN),对于插入，为了能实现常数时间的插入，必定需要改变其数据结构。
二叉搜索树刚好满足以上的所有的需求，但是对于这个，应该不算是严格意义的插入排序了，应是更宽泛的定位—-基于比较的排序。

第一，其本身定义就支持二分查找。
同时查找到对应的值之后，即可插入，所以插入的时间为常数项O(1)。
对于其频繁的插入删除导致的性能降低，目前的排序涉及不多

总结

复杂度: O(nlgn)
移动次数: O(1)
比较次数 O(lgn)

实现
首先将数据构造为二叉搜索树，之后再进行中序遍历即可。

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None

    def insert(self, newData):
        """
        插入数据
        # edage case: 若是value相同如何解决 Word天
        :param newData:
        :return:
        """
        if newData == self.data:
            return False
        elif newData < self.data:
            if self.leftChild == None:
                self.leftChild = TreeNode(newData)
            else:
                self.leftChild.insert(newData)
        else:
            if self.rightChild == None:
                self.rightChild = TreeNode(newData)
            else:
                self.rightChild.insert(newData)

    # 以下的前中后遍历均为递归的遍历
    def preOrder(self):
        """
        前序遍历
        根左右
        :return:
        """
        print(self.data)
        if self.leftChild:
            self.leftChild.preOrder()
        else:
            self.rightChild.preOrder()

    def inOrder(self):
        """
        中序遍历
        左根右
        :return:
        """
        if self.leftChild:
            self.leftChild.inOrder()
        print(self.data)
        if self.rightChild:
            self.rightChild.inOrder()

References

算法新解
算法第四版

插入排序

插入排序

前言

算法思想

插入

基本插入算法

优化一： 使用鶸二分查找

优化三： 终极进化之二叉搜索树

References

优化一：使用鶸二分查找

优化三：终极进化之二叉搜索树