[数据结构与算法]C++一本通基础算法：数据排序

1.快速排序（quick sort）

算法概述：运用二分法将需要排序的数组拆分进行排序。

时间复杂度：O（n * log(n)）

算法特点：速度快，时间复杂度稳定，排序算法不稳定，排序的常用算法

所属库函数：algorithm

调用方法

sort (a,a + 10,cmp);   //第一个为排序的起始位置，第二个为排序的结束位置，第三个为排序规则

sort函数除了可以排序整数数组，还可以排序浮点数数组、字符数组、字符串数组和结构体数组。

sort函数排序规则cmp的编写

void cmp (int x,int y) {     //参数的格式由需要排序数组的格式决定，这里以int为例
	return x > y;            //返回值的形式决定了排序的形式
}                            //返回值为升序，排序后的数组也为升序，或其它自定义的顺序

在排序的数组类型不为结构体数组时，cmp可以省略，默认排序为升序。

在数组类型为结构体数组时，cmp不可以省略。

struct peo {                             //当排序类型为结构体时的cmp写法
	int old,k;
	string id;
}a[105];

bool cmp (peo a,peo b) {
	if (a.old >= 60 && b.old >= 60) {
		if (a.old == b.old) return a.k < b.k;
		return a.old > b.old;
	}
	else if (a.old >= 60 || b.old >= 60) return a.old > b.old;
	else return a.k < b.k;
}

2.冒泡排序

算法概述：依次将大数移到最右边，完成排序。

时间复杂度：O（n2）

算法特点：排序算法稳定，时间复杂度不稳定，可以某些解决特定问题

所属库函数：无

代码实现

for (int i = 1;i < n;i++) {            //每一次循环将一个大数移到右边
		for (int j = 1;j <= n - i;j++) {
			if (a[j] > a[j + 1]) {     //比较大小，如果大，那么交换位置
				swap(a[j],a[j+1]);
			}
		}                
	}

3.桶排序

算法概述：将每个数存在与其数组下标相匹配的空间中（桶），然后遍历数组

时间复杂度：O（n）

算法特点：排序算法稳定，时间复杂度稳定，但仅在数据范围小的时候适用，具有很大的局限性，可以解决某些特定问题

所属库函数：无

代码实现

for (int i = 1;i <= n;i++) {    //在桶排序中，下标i表示所对应的数，a[i]表示这个数出现的次数
		int p;
		cin >> p;
		a[p]++;
	}