|
比较次数 |
交换次数 |
空间 |
类型 |
稳定性statble |
适用范围 |
|||||
|
最优 |
平均 |
最坏 |
最优 |
平均 |
最坏 |
|||||
|
冒泡排序 |
n(n-1)/2 |
n(n-1)/2 |
n(n-1)/2 |
0 |
n(n-1)/4 |
n(n-1)/2 |
O(1) |
基于比较排序交换 |
稳定 |
无任何实际使用范围；仅用于比较其他排序性能 |
|
插入排序 |
n-1 |
O(n^2) |
O(n^2) |
0 |
O(n^2) |
O(n^2) |
O(1) |
基于比较 |
稳定 |
当数据基本有序或者元素个数较少： |
|
二叉树排序 |
O(nlogn） |
O(nlogn） |
O(n^2) |
O(n) |
基于比较 |
不稳定 |
二叉树排序过程与快排等价，可分析快排性能 |
|||
|
选择排序 |
n(n-1)/2 |
n(n-1)/2 |
n(n-1)/2 |
0 |
O(n) |
O(n) |
O(1) |
基于比较 |
稳定 |
当比较的耗时，远小于交换的耗时. |
|
堆排序 |
O(nlogn |
O(nlogn） |
O(nlogn） |
O(nlogn） |
O(nlogn） |
O(nlogn） |
O(1) |
基于比较 |
不稳定 |
Top K问题：在一堆数据中选取前K(K>1)个数 |
|
归并排序Merge Sort |
O(nlogn |
O(nlogn） |
O(nlogn） |
O(1） |
O(nlogn） |
O(nlogn） |
O(N) |
基于比较 |
稳定 |
hadoop的reduce过程是一个归并过程（不是归并排序）； |
|
原地归并排序 |
O(nlogn） |
O(nlogn） |
O(nlogn） |
O(1） |
O(nlogn） |
O(nlogn） |
O(1) |
基于比较 |
稳定 |
最常见的是bottom up 归并 |
|
快速排序 |
O(nlogn） |
O(nlogn） |
O(n^2） |
O(1） |
O(nlogn） |
O(n^2） |
O(logn) |
基于比较 |
不稳定 |
|
|
最优 |
平均 |
最坏 |
||||||||
|
计数排序 |
O(n+2^k) |
O(n+2^k) |
O(n+2^k) |
O(n+2^k) |
非基于比较 |
稳定 |
||||
|
基数排序Radix Sort |
O(nk/s) |
O(nk/s) |
O(nk/s) |
O(n) |
非基于比较 |
稳定 |
在字符串中常见.基数排序中，需要使用到计数排序 |
|||
|
桶排序 |
O(n） |
O(nk） |
O(n^2k） |
O(nk) |
非基于比较 |
稳定 |
需要假定原始数据均匀分布于给定范围 |
另外：
-
锦标赛排序
锦标赛排序：是寻找第一和第二元素的最优比较次数的方法。 = N-1+logN，如果是要选择Top K元素，与heapsort基本无异，可以看成是heapsort的特例（较少次数比较的heapsort）
这个排序属于选择排序，因为每次都决定哪个元素需要和哪个比较或者交换，该算法思路可以扩展，如赛马问题：
赛马问题，是Top K问题的一个特例.
25匹赛马，5个跑道，也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的3匹马？
这里面，5个跑道，相当于5叉树，锦标赛排序，一次是比较2个元素，所以是2叉树。所以：基本思路是：5个，5个一组比较。
-
归并排序
归并排序可以用于求序列的”逆“。
交换、插入、选择，是比较排序的基本实现方式。交换：通过交换实现2个元素位置的正确性
插入：通过插入方式实现有序过程，因此数据是逐渐增加的过程。选择：是选择哪个元素进行比较或交者交换，在普通的选择排序中，可以不通过交换实现有序过程，比如构造空间O(n),原始序列不变的方式来实现。所以选择排序的一般实现虽然使用交换，但是并不属于基于交换方式的比较排序过程。
-
稳定与不稳定
稳定：稳定的排序是，总有一种实现方式使得对任意序列排序过程稳定。
不稳定：对于给定的排序算法的实现，总可以找到一个序列特例，其结果不稳定。
因此，快排，对case 1排序结果稳定，但并不说明快排是稳定的。
插入排序，如果实现方式中，每次比较<改成<=，这样，排序的结果是不稳定的，但这不能说，插入排序是不稳定的，是实现方式的问题，即，只要找到一种实现方式（用<号，而不是<=号）就可以实现稳定的排序。
-
原地排序
即使用原始序列进行排序，空间O(1)，是衡量空间复杂度的。（注：总体来说，空间复杂度分析，要不时间复杂度分析难很多，而且空间限制通常比时间限制更难解决）。
-
排序的前提
传递性:a<b,b<c那么a<c
反自反性，a<b,那么！(b<a)
任意2个元素可比较
排序：是一个序列的“逆”的个数转换为0的过程。
相关推荐
### 各种排序算法的稳定性和时间复杂度总结 #### 排序算法的稳定性与时间复杂度概述 在计算机科学中，排序算法是基础且重要的组成部分，用于将一系列数据按照特定顺序排列。排序算法的效率通常由其时间复杂度决定...
### 排序算法比较：时间复杂度与稳定性分析 在计算机科学中，排序算法是处理大量数据时不可或缺的一部分。本文将对几种常见的排序算法进行对比分析，包括它们的时间复杂度和稳定性特点，以便读者能够更好地理解每种...
1. 首先产生要进行排序的整形数组（可以保存在文件中以备后用） 2. 调用各种排序方法对数组排序，并...对于更多更高级的排序算法，以后会实现，另外，对于复杂字符串排序，这些简单排序并不适合，请采用更高效的方法
### 排序算法的稳定性和时间复杂度小结 #### 一、引言 排序算法是计算机科学中的基本算法之一，广泛应用于各种场景之中。排序算法不仅关注排序的速度（时间复杂度），还关注排序过程中是否能够保持相等元素原有的...
### 排序算法时间复杂度的研究 #### 引言 排序是计算机科学中的基础操作之一，在数据处理与分析中占据着重要地位。排序算法的好坏直接影响到计算机程序的执行效率，尤其是在处理大规模数据集时更为明显。根据数据...
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
归并排序的时间复杂度始终保持为O(n log n)，是稳定的排序算法。 6. 堆排序（Heap Sort） 堆排序是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的...
在本文档中，作者通过C语言实现了四种不同的排序算法，并对它们的时间复杂度进行了比较。这些排序算法包括直接插入排序、直接选择排序、冒泡排序和快速排序。以下是每种排序算法的详细说明： 1. **直接插入排序...
应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,即求解算法的期望收敛时间,估算了该算法的时间复杂度,结果证明该算法的时间复杂度与所得解的多样性、...
1. 桶内排序的时间复杂度：如果每个桶都使用插入排序，那么每个桶的时间复杂度为O((n/k)²)，因为插入排序在最坏情况下需要O(n²)的时间。所以，所有桶的总时间复杂度为O(k * (n/k)²) = O(n²/k)。 2. 合并桶的...
在实际应用中，对于大规模数据的排序，我们通常会选择时间复杂度更低的算法，如快速排序、归并排序或堆排序等。这些算法在平均情况下能提供O(n log n)的时间复杂度，显著优于选择排序。然而，理解不同排序算法的时间...
然而，递归算法在提供简洁性和直观性的同时，也往往伴随着较高的时间和空间复杂度，尤其是当递归层数较深时，这种复杂度的增加可能会变得不可忽视。 ### 时间复杂度的概念 时间复杂度是衡量算法效率的重要指标之一...
| 数据规模 | 插入排序时间 | 堆排序时间 | | --- | --- | --- | | 10000 | 0.025 | 0.165 | | 20000 | 0.375 | 0.268 | | 40000 | 1.620 | 0.825 | | 80000 | 3.364 | 1.756 | | 160000 | 7.830 | 3.517 | | 320000...
### 快速排序改进算法：时间复杂度的深入解析 #### 快速排序的基本概念与问题 快速排序，由C.A.R.Hoare于1962年提出，是一种高效的排序算法，基于分治策略。它通过选择一个“基准”元素，将数据集分割成两个子集，...
冒泡排序的时间复杂度是O(N^2)。找到第k大的元素只需查看排序后的第k个位置，但这并没有减少整体排序的复杂度。 - 解决方案2：首先对前k个元素进行排序，时间复杂度为O(k^2)。然后逐个检查剩下的(N-k)个元素，如果...
【排序算法性能分析】 在计算机科学中，排序算法是用于重新排列一组数据的算法，使得数据按照特定的顺序排列。...在选择算法时，不仅要考虑时间复杂度，还需要考虑空间复杂度、稳定性、代码实现的复杂性等因素。
4. 算法优化：通过改进算法结构或使用数据结构（如哈希表、堆、树等）来降低时间复杂度，是提高程序效率的重要手段。 5. 时间复杂度分析技巧：包括主项分析、忽略低阶项、常数因子约简等，帮助我们简化表达式，准确...
【排序算法的稳定性和时间复杂度】 排序算法是计算机科学中的基本操作，它涉及将一组数据按照特定的顺序排列。稳定性和时间复杂度是衡量排序算法性能的重要指标。 **稳定性**指的是排序过程中相等的元素在排序后...
- 在排序算法中，稳定性的概念指的是当两个元素具有相同的键值（关键码），在排序后它们的相对顺序保持不变。例如，冒泡排序、插入排序、基数排序和归并排序都是稳定的排序算法，而快速排序是不稳定的，因为它可能...
原始的堆排序算法的时间复杂度为O(n log n)，空间复杂度为O(1)，因为它是一个原地排序算法，不需要额外的存储空间。在构建堆的过程中，每个节点最多需要进行log_2(n)次比较，而调整建新堆时调用Heapadjust过程n-1次...