C++基础算法教程——数据排序（2）

C++基础算法教程——数据排序（2） 欢迎来到沾花把玖的C++算法课堂！

数据排序——插入排序

1.基本思想：

想象打牌时抓牌的情景，为了方便抓牌，抓牌时一般一边抓牌一边按花色和大小插入恰当的位置，当抓完所有的牌时，手中的牌便是有序的，这种排序方法就叫做插入排序。

当读入一个元素时，在已经排序好的序列中，搜寻它的位置，再放入读入的元素。但不能忽略一个重要的问题：在插入这个元素前，应当先将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。

2.动图演示：

例题：

【题目描述】

输入n个数，将这n个数从小到大输出（n<=10000）。

【样例输入】

6

15 83 79 52 68 123

【样例输出】

15 52 68 79 83 123

【分析】

当n=6时，数组a中的6个元素是：15，83，79，52，68，123。执行插入排序程序后，其数据变动情况：

第0步：[15] 83 79 52 68 123

第1步：[15 83] 79 52 68 123

第2步：[15 79 83] 52 68 123

第4步：[15 52 79 83] 68 123

第5步：[15 52 68 79 83] 123

第6步：[15 52 68 79 83 123]

排序结束！

以下是代码：

#include
using namespace std;
const int MAXN=10010;
int main(){
    int n,i,j,l;
    double temp,a[MAXN];
	cin>>n;
	for(i=1;i<=n;i++)
	    cin>>a[i];
		for(i=1;i<=n;i++){
			for(j=i-1;j>=1;j--)     //在前面有序区中为a[i]找合适的插入位置
			    if(a[j]j;l--)
				    a[l+1]=a[l];     //将a[i]放在正确位置上
				a[l+1]=temp;
			}
		}
	    for(i=1;i<=n;i++)
	        cout<

本文内容为小编自己汇总，内容可能会有错误或疏漏，感谢大家的提议！

记得点赞和关注哦~