一.冒泡排序.插入排序.希尔排序.快速排序与归并排序 效率概要: 冒泡排序是蛮力法,使用两层嵌套循环,基本效率为 O(n^2) 插入排序是减治法,第一趟排序,最多比较一次,第二趟排序,最多比较两次,以此类推,最后一趟最多比较N-1次,因此有1+2+3+…+N-1 = N*(N-1)/2.然而,因为在每一趟排序发现插入点之前,平均只有全体数据项的一半真的进行了比较,所以除以2最后是N*(N-1)/4. 对于随机顺序的数据,插入排序也需要O(N²)的时间级.当数据基本有序,插入排序几乎只需要O(N)