# 计数排序

计数排序是一种线性时间复杂度的排序算法，适用于一定范围内的整数排序。它的基本思想是通过统计每个元素出现的次数，然后根据这些统计信息将元素排列起来。

# 题目：

学校正在选举学生会成员，有 n（≤999n≤999）名候选人，每名候选人编号分别从 11 到 n*，现在收集到了 m*（≤2000000m≤2000000）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序

# 分析

将选手的选票数保存在以选手号为下标的数组里，对应的值就是选票

注意：题目是按照票数字数由小到大排序

# 代码

	// 计数排序
	#include <iostream>
	using namespace std;

	int a[1000] = {0}; // 声明一个长度为 n 的数组 a，用于记录每个候选人获得的选票数量

	int main()
	{
	int n, m; // 候选人数量和选票数量
	cin >> n >> m;

	int candidate; // 声明一个变量用于记录每张选票上的候选人编号
	for (int i = 0; i < m; i++)
	{
	cin >> candidate;
	a[candidate]++; // 将对应位置的数组 a 的值加 1
	}

	for (int i = 1; i <= n; i++)
	{
	for (int j = 0; j < a[i]; j++)
	{
	cout << i << " "; // 输出相应次数的候选人编号
	}
	}

	return 0;
	}

# 选择、冒泡、插入排序

这三种排序时间复杂度并不佳，数据规模较大时可能耗时久，比赛一般不用。

用扑克牌举例

# 选择排序（Selection Sort）：

选择排序过程是这样的：每次从未排序的牌堆中选择最小的牌，然后放到已排序牌的末尾。
重复这个过程，直到所有牌都被放置在正确的位置上。
选择排序是不稳定的排序算法，其时间复杂度为 O (n^2)。

选择排序的代码示例（C++）：

	void selectionSort(int arr[], int n) {
	for (int i = 0; i < n-1; i++) {
	int minIndex = i;
	for (int j = i+1; j < n; j++) {
	if (arr[j] < arr[minIndex]) {
	minIndex = j;
	}
	}
	swap(arr[i], arr[minIndex]);
	}
	}

# 冒泡排序（Bubble Sort）：

冒泡排序过程是这样的：相邻的两张牌进行比较，如果它们的顺序错误，则交换它们的位置。最大 / 小的牌到最后面了。
重复这个过程，直到所有牌都按照正确的顺序排列。
冒泡排序是稳定的排序算法，其时间复杂度为 O (n^2)。

冒泡排序的代码示例（C++）：

	void bubbleSort(int arr[], int n) {
	for (int i = 0; i < n-1; i++) {
	for (int j = 0; j < n-i-1; j++) {
	if (arr[j] > arr[j+1]) {
	swap(arr[j], arr[j+1]);
	}
	}
	}
	}

# 插入排序（Insertion Sort）：

插入排序过程是这样的：将一张新牌插入到已排序的牌堆中的正确位置。
重复这个过程，直到所有牌都按照正确的顺序排列。
插入排序是稳定的排序算法，其时间复杂度为 O (n^2)。

插入排序的代码示例（C++）：

	void insertionSort(int arr[], int n) {
	for (int i = 1; i < n; i++) {
	int key = arr[i];
	int j = i - 1;
	while (j >= 0 && arr[j] > key) {
	arr[j+1] = arr[j];
	j--;
	}
	arr[j+1] = key;
	}
	}

# 快速排序

比赛常用排序

快速排序（Quick Sort）是一种常用且高效的排序算法，其基本思想是通过分治的策略将一个大问题拆分为小问题进行解决。

具体步骤如下：

选择一个基准元素。通常情况下，可以选择数组中的第一个元素作为基准。
将数组划分为两个子数组，使得左边的子数组中的元素都小于等于基准元素，右边的子数组中的元素都大于基准元素。这个过程称为分区（Partition）。可以使用双指针法或者挖坑法来实现分区。
对左右子数组分别进行递归调用快速排序。即将左子数组和右子数组作为新的数组执行步骤 1 和步骤 2，直到子数组的长度为 0 或 1，此时说明子数组已经有序。
合并结果。将左子数组、基准元素和右子数组按顺序合并起来。

快速排序的时间复杂度为平均情况下的 O (nlogn)，最坏情况下的时间复杂度为 O (n^2)（当选取的基准元素恰好为最大或最小值时），但是最坏情况出现的概率较低。快速排序是一种原地排序算法，不需要额外的空间开销。

	void quickSort(int arr[], int low, int high) {
	if (low < high) {
	int pivotIndex = partition(arr, low, high); // 将数组进行分区，并获取基准元素的索引
	quickSort(arr, low, pivotIndex - 1); // 对左侧子数组进行快速排序
	quickSort(arr, pivotIndex + 1, high); // 对右侧子数组进行快速排序
	}
	}

	int partition(int arr[], int low, int high) {
	int pivot = arr[low]; // 选择第一个元素作为基准
	int i = low, j = high;

	while (i < j) {
	while (i < j && arr[j] >= pivot) { // 在右侧找到小于基准的元素的索引
	j--;
	}
	arr[i] = arr[j];

	while (i < j && arr[i] <= pivot) { // 在左侧找到大于基准的元素的索引
	i++;
	}
	arr[j] = arr[i];
	}

	arr[i] = pivot; // 将基准元素放置在正确的位置
	return i; // 返回分区后基准元素的索引
	}

# sort 排序

，STL（标准模板库）中提供了 sort 和 unique 算法来进行排序和去重操作。

sort 算法用于对指定范围内的元素进行排序，默认按照升序进行排序。它的函数原型如下：

	template <class RandomAccessIterator>
	void sort(RandomAccessIterator first, RandomAccessIterator last);

其中， first 和 last 表示要排序的元素范围，通常是使用迭代器指定的数组或容器的起始和结束位置。

例如，对一个整数数组进行排序可以这样使用 sort 算法：

	int arr[] = {5, 2, 8, 3, 1};
	int n = sizeof(arr) / sizeof(arr[0]);
	sort(arr, arr + n);

unique 算法用于移除指定范围内的连续重复元素，使得每个元素只出现一次，并返回新的范围的尾后迭代器。它的函数原型如下：

	template <class ForwardIterator>
	ForwardIterator unique(ForwardIterator first, ForwardIterator last);

其中， first 和 last 表示要去重的元素范围，通常是使用迭代器指定的数组或容器的起始和结束位置。

例如，对一个整数数组进行去重可以这样使用 unique 算法：

	int arr[] = {1, 2, 2, 3, 3, 4, 5, 5};
	int n = sizeof(arr) / sizeof(arr[0]);
	sort(arr, arr + n); // 先排序，再去重
	auto last = unique(arr, arr + n);

在上面的例子中， unique 函数将数组中的连续重复元素移除，并返回新的范围的尾后迭代器 last 。

需要注意的是，使用 unique 算法之前通常需要先对元素进行排序，以确保重复的元素相邻。因此，在调用 unique 之前，往往会配合使用 sort 算法来先对元素进行排序。

算法排序