插入排序

                  

插入排序

Description
插入排序是一种十分常见的排序方法。其基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是一种稳定的排序方法。请你结合数据结构所学知识，实现这种排序方法，并将每一轮的排序结果输出。

Input
第一行输入整数N（1<=n<=100）代表待排序的数据个数。

接下来一行中有N个整数，代表待排序的数据。

Output
第一行输出原始的数据顺序，接下来每一行输出一趟排序的结果（如果顺序没有改变则不输出），直至排序完成，从而实现数据的升序排列。

如果一开始的数据已经有序，则只输出原始数据。

注意，输出的每一个数字后面均带有一个空格。

Sample Input
Copy sample input to clipboard
5
78 24 13 2 99

Sample Output
78 24 13 2 99
24 78 13 2 99
13 24 78 2 99
2 13 24 78 99

-----------------------------------
一开始做这道题的时候，没注意到“如果顺序没有改变则不输出”这句话，被坑了好久。后来终于发现了，写的代码如下

#include<iostream>
using namespace std;

int a[101];
int b[101];

//判断是否排序完成
bool haveSort(int *a,int size)
{
	for(int i = 0;i < size-1;i++)
	{
		if(a[i]>a[i+1])
			return false;
	}
	return true;
}

//判断进行排序后序列是否有改变
bool change(int *a,int *b,int size)
{
	for(int i = 0;i < size;i++)
	{
		if(a[i] != b[i])
			return true;
	}
	return false;
}

int main()
{
	int n;
	cin>>n;

	for(int i = 0;i < n;i++)
		cin>>a[i];

	//输出原始数据
	for(int i = 0;i < n;i++)
		cout<<a[i]<<" ";
	cout<<endl;

	if(haveSort(a,n))
		return 0;
	else
	{
		//插入排序
		for(int i = 1;i < n;i++)
		{
			for(int i = 0;i < n;i++)
				b[i] = a[i];			
			
			int temp = a[i];
			int j = i-1;

			while(j>=0 && temp < a[j])
				a[j+1]=a[j],j--;
			a[j+1]=temp;
					
			//每次插入排序后输出
			if(change(a,b,n))
			{
				for(int i = 0;i < n;i++)
					cout<<a[i]<<" ";
				cout<<endl;
			}
			
			//判断是否已经排好序，若排好则停止
			if(haveSort(a,n))
				return 0;
		}
	}

	return 0;
}