一、插入排序法

       插入排序法类似于打扑克时单手拿牌，用另一只手把牌一张张抽出来再插入前面已拍好序的手牌中，并一直重复这一动作，直到排序完成。

       请编写一个程序，用插入排序法将包含N个元素的数列a按升序排列。 

输入 在第1行输入层定义数组长度的整数N。在第2行输入N个整数，以空格隔开。

输出 输出总共N行。插入排序法每个计算步骤的中间结果各占用1行。数列的各元素之间空1个空格。请注意，行尾元素是后的空格等多余的空格和换行会被认定为Presentation Error。限制  1≤N≤100                                                                                                                                   0≤a的元素≤1000

输入示例     6                                                                                                                                                5  2  4  6  1  3

输出示例                                                                                                                                         2  5  4  6  1  3                                                                                                                             2  4  5  6  1  3                                                                                                                             2  4  5  6  1  3                                                                                                                             1  2  4  5  6  3                                                                                                                             1  2  3  4  5  6                                                                                                                                 

       此过程可以引用一个i=1进行一个外部循环，将a[i]的值临时存入变量v中。再引用一个j进行一个内部循环，j=i-1开始自减（目的是将把v左边所有比他大的数向右移动）。j=-1或a[j]≤v时结束循环，并将v插入当前j+1的位置。 

#include<iostream>
using namespace std;
void insert(int x[],int N);
int main()
{
    int n,a[100];
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    insert(a,n);//引用插入排序法的函数 
    return 0;
}

void insert(int x[],int N) 
{
	int v,j;
	for(int i=1;i<N;i++)
	{
		v=x[i];
		j=i-1;
		while(j>=0&&x[j]>v)//通过循环将v插入前面已排好序列 
		{
			x[j+1]=x[j];
			j--;
		}
		x[j+1]=v;
	}
	for(int i=0;i<N;i++) 
    {
    	if(i)cout<<' ';//在相邻元素之间输出一个空格 
		cout<<x[i]; 
	}
}

 二、冒泡排序法

 冒泡排序法为不使用flag的和使用flag的。

       两种方法基本相同。都是通过两两比较大小，将较大的数像冒泡泡一样一点点移向右边，达到升序效果。使用flag即定义一个bool型flag变量。如果为正，进行内部循环；如果为负，跳出内部循环。

        请编写一个程序，读取数列a，利用冒泡排序法将其按升序排列并输出。另外请报告执行元素交换的次数。

输入 在第1行输入定义数组长度的整数n。在第2行输入n个整数，以空格隔开。

输出 输出总计2行。请在第一行输出排序后的数列。数列相邻要素用1个空格隔开。第2行输出元素交换的次数。

限制 1≤n≤100                                                                                                                                    0≤a的元素≤100

输入示例

6

6  5  4  1  3  2

输出示例

1  2  3  4  5  6

13

 下面来看不使用flag的代码。

#include<iostream>
using namespace std;
int bubblesort(int a[],int);
int main()
{
	int a[100],n,sw;
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>a[i];
	sw=bubblesort(a,n);//sw记录交换次数 
	cout<<"\n交换次数:"<<sw;
	return 0;
}

int bubblesort(int a[],int n)
{
	int sw=0;
	for(int i=0;i<n-1;i++)//两个循环将较大数移像右边 
    for(int j=0;j<n-i-1;j++)
	{
    	if(a[j]>a[j+1])
	   	{
	   	swap(a[j],a[j+1]);//交换相邻元素 
	   	sw++;
		}
	}
	for(int i=0;i<n;i++)
	{
		if(i)cout<<' ';
		cout<<a[i];
	}
	return sw;
}

再来看看使用flag的代码。 

#include<iostream>
using namespace std;
int bubblesort(int a[],int n);
int main()
{
	int a[100],n,sw;
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>a[i];
	sw=bubblesort(a,n);
	for(int i=0;i<n;i++)
	{
		if(i)cout<<' ';
		cout<<a[i];
	}
	cout<<endl;
	cout<<"\n交换次数:"<<sw;
	return 0;
}

int bubblesort(int a[],int n)
{
	int sw=0;
	bool flag=1;
	for(int i=0;flag;i++)
	{
		flag=0;
		for(int j=0;j<n-1-i;j++)
		{
			if(a[j]>a[j+1])
			{
				swap(a[j],a[j+1]);
				flag=1;
				sw++;
			}
		}
	}
	return sw;
}

三、选择排序法

       选择排序法是一种非常直观的算法，它会在每个计算步骤中选出一个最小值，进而完成排序。

       请编写一个程序，读取数列a，利用选择排序法将其按升序排列并输出执行交换次数。

输入 在第1行输入定义数组长度的整数n。在第2行输入n个整数，以空格区分。

输出 输出总计2行。请在第1行输出排序后的数列。数列相邻元素用1个空格隔开。第二行输出交换次数。 

限制 1≤n≤100
        0≤a的元素≤100

输入示例
6

4  1  3  6  2  5

输出示例

1  2  3  4  5  6

4

 这里我们要注意，选择排序法属于不稳定的排序算法。因为如果有两个相同的数，我们暂且假设3a，3b。但是通过选择排序之后，则会变成3b，3a。

#include<iostream>
using namespace std;
int selectionsort(int a[],int n);
int main() 
{
	int a[100],n,sw;
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>a[i];
	sw=selectionsort(a,n);
	for(int i=0;i<n;i++)
	{
		if(i>0)cout<<' ';
		cout<<a[i];
	}
	cout<<"\n"<<sw;
	return 0;
}

int selectionsort(int a[],int n)
{
	int minj,sw=0,i,j;
	for(i=0;i<n-1;i++)
	{
		minj=i;
		for(j=i;j<n;j++)
		{
			if(a[j]<a[minj])minj=j;//记录每次选择出来的最小数下标 
		}
		swap(a[i],a[minj]);
		if(i!=minj)sw++;
	}
	return sw;
}