[数据结构与算法]CC++ qsort函数和sort函数

qsort() 函数和 sort() 函数实现排序功能，前者是 C 语言内容，后者是 C++ 内容，下面逐一讲解。

qsort()

先来看一个对数组 arr 排序的例子。qsort() 函数在 stdlib.h 库中，使用时要包含该库文件。

#include <stdio.h>
#include <stdlib.h>

int cmp1(int * a, int * b)
{
	return *a - *b;
}

int main()
{
	int arr[5] = {3, 1, 5, 2, 4};
	qsort(a, 5, sizeof(int), cmp1);
	
	int i;
	for (i = 0; i < 5; i++)
		printf("%i ", a[i]);
	return 0;
} 

qsort() 函数有 4 个参数。第 1 个参数表示要排序的数组地址，这里参数为 arr，表示对数组 arr 排序。第 2 个参数表示要排序的元素个数，数组里有 5 个元素，所以为 5。第 3 个参数表示每个元素的大小（单位字节），通过 sizeof() 运算符计算 int 类型的字节数。第 4 个参数表示比较函数，形参为指针类型，返回值小于 0，表示 a 要在 b 的左侧，也即从小到大排序；大于 0 则相反；等于 0 顺序不确定。

假设对结构体 arr_s 排序，优先按照结构体中第 1 个元素大小排序，当第 1 个元素大小相等时，按第 2 个元素大小排序。

struct node
{
	int v1;
	int v2;
};

int cmp2(struct node * s1, struct node * s2)
{
	if (s1->v1 != s2->v1)
		return s1->v1 - s2->v1;
	return s1->v2 - s2->v2;
}

int main()
{
	struct node arr_s[5] = { {2, 3}, {1, 2}, {2, 2}, {3, 2}, {1, 1} };
	qsort(arr_s, 5, sizeof(struct node), cmp2);
	for (i = 0; i < 5; i++)
		printf("(%i, %i) ", arr_s[i].v1, arr_s[i].v2);
	return 0;
} 

将结构体改为二维数组的写法。

int cmp3(int * a, int * b) 
{
	if (a[0] != b[0])
    	return a[0] - b[0];
    return a[1] - b[1];
}

int main()
{	
	int arr2[5][2] = { {2, 3}, {1, 2}, {2, 2}, {3, 2}, {1, 1} };
	qsort(arr2, 5, sizeof(arr2[0]), cmp3);
	for (i = 0; i < 5; i++)
		printf("(%i, %i) ", arr2[i][0], arr2[i][1]);
	printf("\n");
	return 0;
} 

注意第 3 个参数的变化，由于是以行为单位排序，那么元素的大小是一行的大小。

严格来说，qsort() 函数的形参应该是 const void *，cmp1() 函数的写法应当如下，需要将形参进行强制转化。

int cmp4(const void * a, const void * b)
{
	int * p1 = (int *) a;
	int * p2 = (int *) b;
	return *p1 - *p2;
}

sort()

sort() 函数是 C++ 的内容，使用时需要包含 algorithm 库，并且要使用 std 命名空间。同样实现对一维数组排序。

int main()
{
	int arr[5] = {3, 1, 5, 2, 4};
	sort(arr, arr + 5);
	for (int i = 0; i < 5; i++)
		cout << arr[i] << " ";
	cout << endl;
	return 0;
}

sort() 函数只需要 2 个参数，第 1 个参数是数组首地址，第 2 个参数表示结束地址，默认情况下是升序排序。如果需要降序排序，则需要自行实现 cmp() 函数。

bool cmp1(int a, int b)
{
	return a > b;
}

int main()
{
	int arr[5] = {3, 1, 5, 2, 4};
	sort(arr, arr + 5, cmp1);
	for (int i = 0; i < 5; i++)
		cout << arr[i] << " ";
	cout << endl;
	return 0;
}

利用 sort() 函数实现对结构体排序，必须传入 cmp() 函数。

struct node
{
	int v1;
	int v2;
};

bool cmp2(struct node s1, struct node s2)
{
	if (s1.v1 != s2.v1)
		return s1.v1 < s2.v1;
	return s1.v2 < s2.v2;
}

int main()
{
	struct node arr_s[5] = { {2, 3}, {1, 2}, {2, 2}, {3, 2}, {1, 1} };
	sort(arr_s, arr_s + 5, cmp2);
	for (int i = 0; i < 5; i++)
		cout << "(" <<arr_s[i].v1 << ", " << arr_s[i].v2 << ") ";
	cout << endl;
	
	return 0;
}

sort() 函数无法直接对二维数组排序，可以构造一个指针数组，其中每个指针元素都指向一个一维数组，同样需要自行完成 cmp() 函数。

bool cmp3(int a[], int b[])
{
	if (a[0] != b[0])
		return a[0] < b[0];
	return a[1] < b[1];
}

int main()
{
	int * arr2[5];
	int arr20[2] = {2, 3};
	int arr21[2] = {1, 2};
	int arr22[2] = {2, 3};
	int arr23[2] = {3, 2};
	int arr24[2] = {1, 1};
	arr2[0] = arr20;
	arr2[1] = arr21;
	arr2[2] = arr22;
	arr2[3] = arr23;
	arr2[4] = arr24;
	
	sort(arr2, arr2 + 5, cmp3);
	for (int i = 0; i < 5; i++)
		cout << "(" <<arr2[i][0] << ", " << arr2[i][1] << ") ";
	cout << endl;
	
	return 0;
}

使用 C++ 中 vector 的 vector 更为简便。

bool cmp4(vector<int> a, vector<int> b)
{
	if (a[0] != b[0])
		return a[0] < b[0];
	return a[1] < b[1];
}

int main()
{
	vector<vector<int> > vec({ {2, 3}, {1, 2}, {2, 2}, {3, 2}, {1, 1} });
	sort(vec.begin(), vec.end(), cmp4);

	for(auto v : vec)
		cout << "(" <<v[0] << ", " << v[1] << ") ";
	cout << endl;
	
	return 0;
}