插入排序的基本思想是:将数组的第一个数认为是有序数组,从后往前(从前往后)扫描该有序数组,把数组中其余n-1个数,根据数值的大小,插入到有序数组中,直至数组中的所有数有序排列为止。这样的话,n个元素需要进行n-1趟排序!!!
举个例子:4个数字4,6,7,5进行从大到小的排序。前插排序法具体过程如下:
把第一个数4插入到空的有序数组中的第一个位置上,得到新数字序列4;
第一趟:从后往前扫描有序数组,将第二个数字6和有序数组中的4进行比较,6大于4,此时将4后移一个位置。此时已经扫描完有序数组中的数,将6插入到4的前面(有序数组的第一个位置),得到新数字序列6,4;
第二趟:从后往前扫描有序数组,先将第三个数字7和有序数组中的4进行比较,7大于4,此时将4后移一个位置;再将7和有序数组中的6进行比较,7大于6,此时将6后移一个位置。此时已经扫描完有序数组中的数,将7插入到6的前面(有序数组的第一个位置),得到新数字序列7,6,4;
第三趟:从后往前扫描有序数组,先将第四个数字5和有序数组中的4进行比较,5大于4,此时将4后移一个位置;再将5和有序数组中的6进行比较,5小于6,由于有序数组就按照从大到小排列的,此时直接把5插入到4的前面即可!不需要再和7进行比较!最后,得到新数字序列7,6,5,4;
上代码!!!
#include<iostream> #include<cstdio> using namespace std; #define N 5 int a[N];//有序数组 int main ( ) { int i, k, x; printf("Please input %d numbers:\n",N); for (i=0; i<N; i++) { scanf ("%d", &x); for ( k=i; k>0; k-- ) { /* 从后向前比较 */ if ( a[k-1] > x ) //x前面的数比它大 a[k]=a[k-1]; /* 将大数向后移动*/ else break; /* 找到插入的位置,退出 */ } a[k] = x; /* 完成插入操作 */ } for (i=0; i<N; i++) printf("%d ", a[i]); return 0; }
原文:https://www.cnblogs.com/swithun333/p/12520942.html