插入排序

算法分析

序列的第一个元素，肯定是有序的，把第二个元素和第一个元素相比，插入到合适的位置，这样前两个元素就有序了，接着，把第三个元素插入到前面包含两个元素的有序列表中，以此类推，直至插完第n个数据。

• 在最好的情况下，即序列已经是排好序的情况下，每次比较一次就退出while循环，则总比较次数是n-1次，时间复杂度是O(n)
• 在最坏的情况下，即每次while循环都要比较到第一个元素，则：
  第一次循环，比较了1次；
  第二次循环，比较了2次；
  ...
  第n-1次循环，比较了n-1次；
  总的比较次数是1+2+3+...+(n-1)= n(n-1)/2。
  我们上面所求得的n(n-1)/2，其时间复杂度，最大的影响因子是n^{2/2，故其时间复杂度是O(n}2)。

代码实现

def insertSort (listx):
    xLen = len (listx)
    for i in range (1, xLen):
        j = i - 1
        # 把listx[i] 和前面的元素进行比较，插入到合适的位置
        while j >= 0:
            if listx[j] > listx[j + 1]:
                listx[j], listx[j + 1] = listx[j + 1], listx[j]
                j -= 1
            else:
                break
    return listx

if __name__ == '__main__':
    print insertSort ([77, 45, 3, 34, 4, 3, 454, 87])