首页 > 代码库 > 【Algorithm】插入排序
【Algorithm】插入排序
一. 算法描述
插入排序具体算法描述如下:
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
举个例子:5 7 6 4 3 8
第一趟:5 7 6 4 3 8 =》5 7 6 4 3 8
第二趟:5 7 6 4 3 8 =》5 6 7 4 3 8
第三趟:5 6 7 4 3 8 =》4 5 6 7 3 8
第四趟:4 5 6 7 3 8 =》3 4 5 6 7 8
第五趟:3 4 5 6 7 8 =》3 4 5 6 7 8
三. 算法实现
算法实现1
/** author:Knife* time:2014.06.13 16:07* Algorithm:插入排序(从前向后查找)*/#include<stdio.h>void main_insertSort(){ int intArr[] = {8,3,6,4,2,9,5,4,1,7}; int n = sizeof(intArr)/sizeof(intArr[0]); // 计算整型数组的长度 int i,j,k,tmp; for(i = 1; i < n; i++){ for( j = 0; j < i; j++){ if(intArr[i] < intArr[j]){ // 插入位置j tmp = intArr[i]; for(k = i; k>j; k--){ intArr[k] = intArr[k-1]; } intArr[j] = tmp; // 插入 } } } // 打印输出 for(i=0; i<n; i++){ printf("%d ",intArr[i]); } printf("\n");}
算法实现2
/** author:Knife* time:2014.06.13 16:07* Algorithm:插入排序(从后向前查找)*/#include<stdio.h>void main_1(){ int intArr[] = {8,3,6,4,2,9,5,4,1,7}; int n = sizeof(intArr)/sizeof(intArr[0]); // 计算整型数组的长度 int i,j,tmp; //插入排序 for(i = 1; i < n; i++){ tmp = intArr[i]; j = i-1; while(j>=0 && (tmp < intArr[j])){ // 插入位置 intArr[j+1] = intArr[j]; j--; } intArr[j+1] = tmp; // 插入操作 } // 打印输出 for(i=0; i<n; i++){ printf("%d ",intArr[i]); } printf("\n");}
算法实现3
#include<stdio.h>/** author:Knife* time:2014.06.13 16:43* Algorithm:插入排序(二分查找)*/void main(){ int intArr[] = {8,3,6,4,2,9,5,4,1,7}; int n = sizeof(intArr)/sizeof(intArr[0]); // 计算整型数组的长度 int i,j,low,high,mid,temp; for(i = 1; i < n; ++i){ low = 0; high = i-1; while(low <= high){ //使用二分查找,寻找插入的位置 mid = low + ((high-low) >> 1); //这种写法,有效避免溢出 if(intArr[i] > intArr[mid]){ low = mid + 1; }else{ high = mid - 1; } } temp = intArr[i]; for(j = i; j > low; j--){ //移动元素 intArr[j] = intArr[j-1]; } intArr[low] = temp; //在合适位置,插入。这里为什么是 low? 得仔细想想(答案在这里http://blog.csdn.net/zhangxiangdavaid/article/details/27373183)! } // 打印输出 for(i = 0; i < n; i++){ printf("%d ",intArr[i]); } printf("\n");}
四. 算法分析
- 平均时间复杂度:O(n^2)
- 空间复杂度:O(1) (用于记录需要插入的数据)
- 稳定性:稳定
参考资料
[1] http://blog.csdn.net/zhangxiangdavaid/article/details/27373183
[2] http://blog.csdn.net/cjf_iceking/article/details/7916194
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。