seekerhit 2020-02-13
直接插入排序:通过构建有序序列,对于未排序数据,选出第一个元素,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序因而在从后向前扫描过程中,
需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
我们可以吧一个序列分为有序区段和无序区段,如图:
#include<bits/stdc++.h> using namespace std; int a[105]; int n; //从0开始 ,结果为升序的算法 void insert_sort(int a[],int n) { int i,j,temp; j=0; for(i=1;i<n;i++) { temp=a[i]; j=i-1; while(j>=0&&temp<a[j]) //在有序序列里从后往前扫描依次比较 { a[j+1]=a[j]; //若比当前值小,有序序列空出一个空间,最后一个元素后移 j--; } a[j+1]=temp; //将无序序列中的元素插入到有序序列中 } } int main() //输出测试 { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); insert_sort(a,n); for(int i=0;i<n;i++) { printf("%d",a[i]); if(i!=n-1) printf("-"); else printf("\n"); } }