『算法-ACM 竞赛-疯子的算法总结』6.1 简单排序总 选择排序+插入排序+比较排序+冒泡排序

一、数组的排序算法

1.选择排序

选择排序是指每次选择所需排序数组中的最大值或者最小值（根据排序方式选择，从大到小选最大，从小到大选最小），将这个元素与前面没有进行排序的元素交换。
下面以 1 4 2 5 9 6 这些乱序元素，来表现排序过程。
第一次排序 9 4 2 5 1 6
第二次排序 9 6 2 5 1 4
第三次排序 9 6 5 2 1 4
第四次排序 9 6 5 4 1 2
第五次排序 9 6 5 4 2 1
用一段程序实现以上过程
以由大到小为例

{
	int i,j;				/*定义主函数局部变量*/
	int a[6];				/*开设容量为6的数组用于存入数据*/
	int iTemp;				/*定义暂时存储最值的变量*/
	int iPos;				/*定义用于存储最值位置的变量*/
	for(i=0;i<6;i++)
		cin>>a[i];			/*输入数组的值*/
	for(i=0;i<5;i++)		/*当剩余一个元素时循环即可停止，最后一个元素必定为最值*/
	{
		iTemp=a[i];			/*假设最值为第i个元素，开始时假设为第一个元素，0#位置*/
		iPos=i;	 			/*最值位置为i*/
		for(j=i+1;j<6;j++)	/*从最值的下一个元素开始循环，直到找到一个值比最大值还大的值*/
		{
			if(iTemp<a[j])	/*当找到那个值时*/
			{
				iTemp=a[j];/*重新记录最小值*/
				iPos=j;		/*记录最值位置为*/
			}
		}
		a[iPos]=a[i];
		a[i]=iTemp;			/*交换最大最小值*/
	}
	for(i=0;i<6;i++)
		cout<<a[i];			/*输出数组的值*/
	return 0;
}

2.冒泡排序法

冒泡排序法是指在排序是比较相邻两个元素的数值，换位置（从大到小，大在前。从小到大，小在前。）下面仍以 1 4 2 5 9 6 这些乱序元素为例
以由大到小排序
第一排序过程 sec1        4 1 2 5 9 6 （1/4 比较）
                      sec2        4 2 1 5 9 6 （1/2 比较）
                      sec3        4 2 5 1 9 6 （1/5 比较）
                      sec4        4 2 5 9 1 6   (1/9 比较）
                      sec5        4 2 5 9 6 1 （1/6 比较）
第二排序过程 sec1        4 2 5 9 6 1 （4/2 比较）
                      sec2        4 5 2 9 6 1（2/5 比较）
                      sec3        4 5 9 2 6 1 （2/9 比较）
                      sec4        4 5 9 6 2 1   (6/9 比较）
                      sec5        4 5 9 6 2 1 （2/1 比较）
第三排序过程：5 9 6 4 2 1（中间过程略）
第四排序过程：9 6 5 4 2 1（中间过程略）
第五排序过程：9 6 5 4 2 1（中间过程略）
虽然这个过程在四过程时就已经完成，这是针对特殊情况，一般情况要进行 n-1 此过程才能完全排序。
用程序实现上述过程

{
	int i,j;
	int iTemp;
	int a[6];
	for(i=0;i<6;i++)
		cin>>a[i];
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++)
		{
			if(a[j]<a[j+1])		/*比较相邻元素的值*/
			{
				iTemp=a[j+1];
				a[j+1]=a[j];
				a[j]=iTemp;			/*交换相邻元素的值*/
			}
		}
	}
	for(i=0;i<6;i++)
		cout<<a[i];
	return 0;
}

3.交换排序法

交换排序法，将每一位数于后边的数一一比较，如果发现符合交换条件的元素就进行交换；下面仍以下面仍以 1 4 2 5 9 6 这些乱序元素为例
以由大到小排序
第一次排序 1 与 4 比较，1 小于 4 交换 4 1 2 5 9 6。4 与 2 比较，4 大于 2 继续。4 与 5 比较，4 小于 5，交换 5 1 2 4 9 6。5 与 9 比较，5 小于 9，交换 9 1 2 4 5 6。9 与 6 比较，9 大于 6 继续。
第二次排序 1 与 2 比较，1 小于 2，交换 9 2 1 4 5 6。2 与 4 比较，2 小于 4 交换 9 4 1 2 5 6。4 与 5 比较，4 小于 5，交换 9 5 1 2 4 6。5 与 6 比较，5 小于 6，交换 9 6 1 2 4 5 。
第三次排序 9 6 5 1 2 4
第四次排序 9 6 5 4 1 2
第五次排序 9 6 5 4 2 1
用程序实现

 {
	int i,j;
	int iTemp;
	int a[6];
	for(i=0;i<6;i++)
		cin>>a[i];
	for(i=0;i<5;i++)
    {
        for(j=i+1;j<6;j++)
        {
            if(a[i]<a[j])	   /*寻找符合条件的值*/
            {
                iTemp=a[j];
                a[j]=a[i];
                a[i]=iTemp;			/*交换*/
            }
        }
    }
    for(i=0;i<6;i++)
		cout<<a[i];
	return 0;
}

4.插入排序法

插入排序法相对较为复杂，从数组中抽出一个是在前面的数据中选择合适的位置插入。
下面仍以下面仍以 1 4 2 5 9 6 这些乱序元素为例
以由大到小排序
第一次 取出 1 放在第一个位置 1
第二次 取出 4，跟 1 比较大小，大于 1 放在 1 前面。 4 1
第三次取出 2，跟 1 比较大小，比 1 大，则再跟 4 比较大小。小于 4，插入。 4 2 1
第四次取出 5，跟 1 比较大小，大于 1，则再跟前一元素 2 比较，大于 2，则再跟前一元素 4 比较，大于 4，插入。5 4 2 1
第五次 9 5 4 2 1
第六次 9 6 5 4 2 1
用程序实现上述过程

{
	int i,j;
	int iTemp;
	int iPos;
	int a[6];
	for(i=0;i<6;i++)
		cin>>a[i];
	for(i=1;i<6;i++)
    {
        iTemp=a[i];				/*抽出要插入的值*/
        iPos=i-1;
        while(iPos>=0&&iTemp>a[iPos])
        {
            a[iPos+1]=a[iPos];		/*不符合条件i前的元素后移一位*/
            iPos--;
        }
        a[iPos+1]=iTemp;		/*找到插入位置插入*/
    }
    for(i=0;i<6;i++)
		cout<<a[i];
	return 0;
}