直接插入排序

直接插入排序(Straight Insertion Sort)的核心思想是：从只包含1个元素的有序序列开始，不断地将待排序数据元素有序的插入到这个有序序列合适的位置中，直到有序列表包含了所有待排序数据元素为止 。

例子: 对于   3，1，5，7，2，4，9，6

0.初始状态 3，1，5，7，2，4，9，6（共8个数）

　　   有序表：3；无序表：1，5，7，2，4，9，6

　　1.第一次循环，从无序表中取出第一个数 1，把它插入到有序表中，使新的数列依旧有序

　　   有序表：1，3；无序表：5，7，2，4，9，6

　　2.第二次循环，从无序表中取出第一个数 5，把它插入到有序表中，使新的数列依旧有序

　　   有序表：1，3，5；无序表：7，2，4，9，6

　　3.第三次循环，从无序表中取出第一个数 7，把它插入到有序表中，使新的数列依旧有序

　　   有序表：1，3，5，7；无序表：2，4，9，6

　　4.第四次循环，从无序表中取出第一个数 2，把它插入到有序表中，使新的数列依旧有序

　　   有序表：1，2，3，5，7；无序表：4，9，6

　　5.第五次循环，从无序表中取出第一个数 4，把它插入到有序表中，使新的数列依旧有序

　　   有序表：1，2，3，4，5，7；无序表：9，6

　　6.第六次循环，从无序表中取出第一个数 9，把它插入到有序表中，使新的数列依旧有序

　　   有序表：1，2，3，4，5，7，9；无序表：6

　　7.第七次循环，从无序表中取出第一个数 6，把它插入到有序表中，使新的数列依旧有序

　　   有序表：1，2，3，4，5，6，7，9；无序表：（空）

 

直接插入排序是稳定的，算法时间复杂度平均、最坏都是O(n²)  ，最好O(n)，空间复杂度都是O(1);  

#include<iostream> #include<cstdlib> #include<cmath> #include<cstdio> using namespace std; const int maxn =100001; int a[maxn]; void InsertSort(int a[],int N) { int i,j; for(i=1;i<N;i++) { int temp=a[i]; for(j=i-1;j>=0&&temp<a[j];j--) a[j+1]=a[j]; //将较大元素后移 a[j+1]=temp; //temp插入正确的位置 } } int main() { int n; cout<<"输入序列长度:"<<endl; cin>>n; cout<<"输入序列元素:"<<endl; for(int i=0;i<n;i++) cin>>a[i]; InsertSort(a,n); cout<<"输出序列元素:"<<endl; for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0; }

运行结果：