时间复杂度 O(n^2)
比较次数(见下) 正比于N^2 交换次数N
效率比较
插入排序>(略快于)选择排序>冒泡排序
|
|
插入排序 |
表插入排序 |
|
原理 |
简单排序之一 |
利用有序链表插入效率的比较为O(N)的特点 |
|
比较次数MAX |
(N^2-N)/2 |
N |
|
比较次数AVG |
(N^2-N)/4 |
N/2 |
|
复制次数 |
基本等于比较次数 |
复制次数 2N (1次从数组到链表 1次从链表到数组) |
|
优点 |
如果数据基本有序 时间为 O(N) 因为while循环条件为假 |
|
|
缺点 |
|
开辟差不多两倍的空间(数组和链表必须同时存在) 1 有现成的有序链表类可用 2 表插入排序对不太大的数组排序是比较便利的 |
原文：http://www.cnblogs.com/cici-new/p/4665950.html