首页 > 代码库 > 八大排序算法之一插入排序
八大排序算法之一插入排序
基本思想:
将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
效率：时间复杂度：O（n2）,空间复杂度为 O（1）。
下面此题是HDU-1040题：（这里我使用插入排序算法）
#include<iostream>using namespace std;const int N =1005;void sort(int a[],int num);int main(){ int s[N]; int T; cin>>T; while(T--) { int n; cin>>n; for(int j=0;j<n;j++)//输入数字 cin>>s[j]; sort(s,n);//调用排序算法 cout<<s[0]; for(int k=1;k<n;k++) { cout<<" "<<s[k]; } cout<<endl; } return 0;}void sort(int a[],int num)//这是插入排序的代码{ for(int i=1;i<num;i++) if(a[i]<a[i-1]) { int x=a[i]; int j=i; while(j>0&&x<a[j-1]) { a[j]=a[j-1]; j--; } a[j]=x; }}
八大排序算法之一插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。