【c++】桶排序

一、桶排序的含义与理解

桶排序：工作的原理是将数组分到有限数量的桶子里，然后在依次拿出来，使得数组中的数变得有序。

二、代码实现

include<iostring>
using namespace std;

const int MAX = 10001;
int arr[MAX];
int main() {
	int n, t;
	cin >> n;
	for (int i = 0; i <n; i++)
	{
		cin >> t;
		arr[t]++;
	}
	for (int i = 1; i <= 10; i++)
	{
		while (arr[i] > 0) {
			cout << i << "\t";
			arr[i]--;
		}
	}
	cin.get();
	cin.get();
	cin.get();
}

首先，第一个for循环作用是将数字放到“桶”中，arr[t]++的含义便是将相同的数放到桶一个"桶"中，然后用一个for循环再将从1到10数字“倒出来”，注意while循环在这里的条件需要让arr[i]大于0，原因是你一个“桶”放入多少个数就最多只能倒出多少个数。其实桶循环的实现还是比较简单的，主要是需要理解这里的arr[t]++和arr[i]--的含义。

桶循环的时间复杂度为o(n),空间复杂度为o(n),桶循环需要使用到额外更多的空间，而它的时间复杂度就相对用得更少，桶循环一般使用在排序的数较小和有限时，不然会用到太多空间。