疯子的算法总结(六) 简单排序总 选择排序+插入排序+比较排序+冒泡排序

一、数组的排序算法

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;
}