赞
踩
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)。
void InsertSort(int* a, int n){
for(int i = 0; i < n - 1; i++){//用i来调整end
int end = i;//已排序序列[0, end]
int tmp = a[end + 1];//向已排序序列中插入数据a[end + 1],先将未排序数据a[end + 1]保存到tmp
while(end >= 0){//在已排序序列中从后向前扫描,找到合适的插入位置时,退出循环
if(tmp < a[end]){//如果tmp<a[end]则a[end]向后移动(升序)
a[end + 1] = a[end];
end--;
}
else{
break;//因为[0,end]是有序序列,如果tmp>=a[end],则将tmp插入到end+1位置即可
}
}
a[end + 1] = tmp;//退出循环后,将tmp插入找到的合适的位置
}
}
时间复杂度
设有N个元素待排
假设这N个元素是有序的,只需要遍历一遍每个元素,那么最好情况下的时间复杂度为 O ( N ) O(N) O(N)。
假设这N个元素是无序的,那么插入第N个元素时,最坏需要比较N-1次,总的最坏的比较次数为 1 + 2 + 3 + . . . + ( N − 1 ) 1+2+3+...+(N-1) 1+2+3+...+(N−1),等差数列求和,结果为 N 2 / 2 N^{2}/2 N2/2,所以最坏情况下的时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。
空间复杂度
仅仅使用了常数个辅助单元,空间复杂度是O(1);
稳定性
插入排序,不会改变相同元素的相对顺序,所以是稳定的。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。