在ACM中经常需要我们对数据进行处理,排序就是一种,而排序的方式有很多种,这里就把几种方式列出来,供大家参考。排序问题首先要搞清楚的就是外层循环代表的是什么,内层循环代表的是什么,这个问题很关键,然后就是注意循环变量的范围,解决了这俩个问题看下面的代码就很容易了。

#include <iostream>
using namespace std;

#define LENGTH 10

int main()
{
	int arr[LENGTH] = {9,2,4,6,8,3,7,1,0,5};
	int tem;

	//1、选择排序
	//外层循环代表的是要在该位置上放置的合理的值,例如当i=0的时候,内层循环完毕以后这个0位置上放置的
	//就是最小的值,i=1,内层循环完毕在改位置上放置的就是第二个小的值,当倒数第二个值确定了以后最后一个
	//值自然就确定了,所以i的范围如下
	for(int i=0;i<LENGTH-1;i++)
	{
		//内层循环不断的取出各个位置上的数和外层循环位置上的数进行比较
		for(int j=i+1;j<LENGTH;j++)
		{
			if(arr[j] < arr[i])
			{
				tem = arr[i];
				arr[i] = arr[j];
				arr[j] = tem;
			}
		}
	}

	//以下方法实现起来效率更高,之所以效率高是因为找到一个比外循环指针所对应值更小的值时没有马上交换而是把位置先记录下来,内循环结束后再交换
	int k;
    for(int i=0;i<LENGTH-1;i++)
    {
        k=i;//k的作用是记录内部指针一趟比较下来,哪个位置所对应的值比外指针所对应的值小,将该位置存放到k中,默认情况下k的值是外指针对应位置
        for(int j=i+1;j<LENGTH;j++)
        {
            if(arr[j]<arr[k])
				//k=j 记录下最小值的位置
                k=j;
        }
        tem=arr[i];
        arr[i]=arr[k];
        arr[k]=tem;
    }

	for(int i=0;i<LENGTH;i++)
	{
		cout<<arr[i]<<" ";
	}

	return 0;
}
//2、冒泡排序
	//外层循环控制圈数,就是一共需要比较多少趟,n个数,当然比较n-1趟了
	for(int i=1;i<LENGTH;i++)
	{
		//内层循环将前后俩个数进行比较,然后将大的数冒泡到后边,第一趟比较完毕以后最后一个数就是最大的数
		//下一次比较的时候不需要和最后一个数进行比较,所以大家注意下范围
		for(int j=0;j<LENGTH-i;j++)
		{
			if(arr[j+1] < arr[j])
			{
				tem = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = tem;
			}
		}
	}
//3、插入排序
	//外层循环代表要进行插入排序的数,例如i=0就代表将数组中的第零个数拿出来,然后和已经排好序的数进行比较
	//插入到合适的位置
	for(int i=0;i<LENGTH;i++)
	{
		//内层循环代表将外层循环中拿出的那个数和内层循环中排好序的数逐一进行比较
		for(int j=0;j<i;j++)
		{
			//满足条件的话就交换位置,这个时候那个待排序的数就换了,以后的内层循环中会不断的交换数
			//也可以在找到这个位置以后,将后边的数整体向后移动一下
			if(arr[i] < arr[j])
			{
				tem = arr[i];
				arr[i] = arr[j];
				arr[j] = tem;
			}
		}
	}

前面的方法都需要我们自己去实现代码,为了提高效率我们使用STL中提供的一个函数来排序,它就是sort函数,下面看看如何使用。

#include <iostream>
#include <algorithm> //使用sort函数

using namespace std;

#define LENGTH 10

struct Student
{
	char a;
	int age;
};
//函数的返回值必须是bool类型的,参数类型是需要排序的数据类型
bool cmp(struct Student s1,struct Student s2)
{
	if(s1.a != s2.a)
		return s1.a>s2.a;
	else if(s1.age != s2.age)
		return s1.age < s2.age;

	return true;
}

int main()
{
	int arr[LENGTH] = {9,2,44,6,8,3,7,1,0,5};
	double arr_f[LENGTH] = {1.2,4.5,6.2,4.3,7.8,9.0,1.3,4.8,8.7,9.8};
	char arr_c[] = {'e','a','s'};
	char * arr_str[] = {"hello","hi","efj"};
	//需要包含algorithm头文件
	//sort(数组头指针,数组尾指针,比较函数) ,sort可以为多种数据类型的数进行排序,包括整形,实型,字符型,字符串,结构体
	//默认的排序函数是升序排序的,也可以定义自己的排序函数
	sort(arr_f,arr_f+LENGTH);

	for(int i=0;i<LENGTH;i++)
	{
		cout<<arr_f[i]<<" ";
	}
	cout<<endl;

	//使用sort对字符型数据进行排序
	sort(arr_c,arr_c+3);
	for(int i=0;i<3;i++)
	{
		cout<<arr_c[i]<<" ";
	}
	cout<<endl;

	//使用sort对字符串进行排序
	sort(arr_str,arr_str+3);
	for(int i=0;i<3;i++)
	{
		cout<<arr_str[i]<<" ";
	}
	cout<<endl;

	//对结构体进行比较,使用自定义的比较函数
	struct Student arr_stu[] = {{'a',21},{'a',22},{'b',23}};

	sort(arr_stu,arr_stu+2,cmp);
	for(int i=0;i<3;i++)
	{
		cout<<arr_stu[i].a<<arr_stu[i].age<<" ";
	}
	cout<<endl;

	return 0;

}