数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学数据结构中排序方法的比较
在这里，我们将了解一些排序方法。排序技术有200多种。我们将了解其中的一些。一些排序技术是基于比较的排序，一些是非基于比较的排序技术。
基于比较的排序技术包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序等。这些技术被认为是基于比较的排序，因为在这些技术中，值会被比较，并在不同的阶段放置到排序位置。在这里，我们将了解这些技术的复杂度。
| 分析类型 | 冒泡排序 | 选择排序 | 插入排序 | 归并排序 | 快速排序 | 堆排序 |
|---|---|---|---|---|---|---|
| 最佳情况 | O(n2) | O(n2) | O(n) | O(log n) | O(log n) | O(logn) |
| 平均情况 | O(n2) | O(n2) | O(n2) | O(log n) | O(log n) | O(log n) |
| 最坏情况 | O(n2) | O(n2) | O(n2) | O(log n) | O(n2) | O(log n) |
一些排序算法是非基于比较的算法。其中一些是基数排序、桶排序、计数排序。这些是非基于比较的排序，因为在排序时不会比较两个元素。这些技术的实现方式略有不同。现在我们将根据不同类型的分析来了解它们之间的区别。
| 分析类型 | 基数排序（k是最大位数） | 计数排序（k是计数数组的大小） | 桶排序（k是桶的数量） |
|---|---|---|---|
| 最佳情况 | O(nk) | O(n + k) | O(n + k) |
| 平均情况 | O(nk) | O(n + k) | O(n + k) |
| 最坏情况 | O(nk) | O(n + k) | O(n2) |
排序技术也可以使用其他一些参数进行比较。一些排序算法是原地排序算法，一些是非原地排序算法。那些不需要任何额外空间的算法称为原地排序算法。例如，快速排序和堆排序是原地排序算法。但归并排序是非原地排序技术。
一些算法是在线算法，一些是离线算法。如果算法在排序过程中接受新元素，则称为在线排序算法。在上面提到的技术中，插入排序是在线排序技术。
更新于: 2019年8月27日
6K+ 浏览量
广告