[数据结构与算法] 排序

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 排序—桶排序 -> 正文阅读

[数据结构与算法]排序—桶排序

当输入为 $A_{1},A_{2},...,A_{N}$ ，且 $A_{i}\epsilon Z+,A_{i}<M$ ，使用一个大小为M的数组arr，它被初始化为0，当 $A_{i}$ 读入时， $arr[A_{i}]++$ ，当所有输入读取完成后，就可以通过遍历数组的方式将输入按顺序输出，并且这种方法不仅能够对输入进行排序，还能够对输入完成去重工作，这种方法就被称为桶排序，数组中的每个单元就被称作一个桶。由桶排序的原理，可以明显的看出桶排序的缺点：当M过大时，桶排序所需要的额外空间就变得非常大；桶排序只能对正整数进行排序。桶排序的时间复杂度为 $O(M+N)$ ，但当M过大时，使用桶排序可能并不是一个明智的选择，但是当输入为一些很小的数字时，桶排序相比其他排序就显得简单且便捷。

桶排序实现：

//对100以内的20个数进行桶排序
int main() {
	int arr[101] = { 0 };//额外数组
	int size = 20;
	for (int i = 0; i < size; i++) {
		int k;
		scanf("%d", &k);
		arr[k]++;
	}
	for (int i = 0; i < 100; i++) {
		if (arr[i] > 0)
			printf("%d ", i);
	}
	return 0;
}

排序算法总结：

插入排序	时间复杂度为 $O(N^2)$ ，不需要额外的空间，一般输入比较少或是已经基本排序的情况下可以使用插入排序
希尔排序	也称缩小增量排序，时间复杂度为 $O(N^2)$ ，不需要额外的空间，使用sedgewick增量序列的希尔排序时间复杂度可达到 $O(N^\frac{4}{3})$ ，在实践中性能好于堆排序
堆排序	使用二叉堆实现的排序算法，时间复杂度为 $O(NlogN)$ ，不需要额外的空间，在实践中很少使用
归并排序	时间复杂度为 $O(NlogN)$ ，采用递归，所以需要额外的栈空间，一般使用于外部排序
快速排序	时间复杂度为 $O(NlogN)$ ，采用递归，所以需要额外的栈空间，是目前最快的排序算法
桶排序	时间复杂度为 $O(M+N)$ ，需要额外的数组来进行排序，当输入为正整数并且数字较小时可以使用