各种排序算法总结

插入类

将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；

交换类

通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;

选择类

从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;

归并类

通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;

默认方向：从小到大

选择排序：时间复杂度 : O(n^2)

方法是： –首先在所有记录中选出排序码最小的记录，与第一个记录交换 –然后在其余的记录中再选出排序码最小的记录与第二个记录交换 –以此类推，直到所有记录排好序

基础选择排序

template <class Type>
void select(int n,Type array[])
{
	int i,j,tmp,p;
	for(i=0;i<n-1;i++)
	{
		p=i;
		for(j=i+1;j<n;j++)
			if(array[j]<array[p])
				p=j;
		if(p!=i)
		{
			tmp=array[p];
			array[p]=array[i];
			array[i]=tmp;
		}
	}
}

关联数组排序 可用于贪心等

void SelectSort(int n,int *s,int *f)
{
	int i,j,tmp,tmp1,p;

	for(i=0;i<n-1;i++)
	{
		p=i;
		for(j=i+1;j<n;j++)
			if(f[j]<f[p])
				p=j;
		if(p!=i)
		{
			tmp=s[p];
			tmp1=f[p];
			s[p]=s[i];
			f[p]=f[i];
			s[i]=tmp;
			f[i]=tmp1;
		}
	}
}

多维数组选择排序

//可用结构体或者多维数组 此处略

冒泡排序：

普通版：

template <class Type>
void BubbleSort (Type R[] , int n)
{
	int i,j;
    for (i=n;i>0;i--)
    {
		for ( j = 0; j < i-1; j++ )
		{
          	if (R[ j+1 ] < R[ j ])
          	{
				swap(R[ j ] , R[ j+1 ]);
			} //if
		}//for
	} // for
} // BubbleSort

优化版：

template <class Type>
void BubbleSort (Type R[] , int n)
{
	int i,j,change;
    for (i=n;i>0;i--)
    {
		change = false;
		for ( j = 0; j < i-1; j++ )
		{
       		if (R[ j+1 ] < R[ j ])
          	{
				swap(R[ j ],R[ j+1 ]);
				change = true;
	 		} //if
		}
		if(change==false)
			break;
	} // for
} // BubbleSort