|
比较次数 |
交换次数 |
空间 |
类型 |
稳定性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的过程。
相关推荐
### 排序算法时间复杂度的研究 #### 引言 排序是计算机科学中的基础操作之一，主要用于对数据集中的元素按照特定的顺序进行排列。排序算法的效率直接关系到计算机程序的整体性能。根据数据是否完全加载到内存中，...
本文将比较几种排序算法的时间复杂度，包括快速排序、选择排序、直接插入排序和堆排序算法，并在排序数据中快速查找某一数据，给出查找是否成功，以及数据所在的位置信息。 在详细设计中，我们首先来读取文件中的...
### 各种排序算法的稳定性和时间复杂度总结 #### 排序算法的稳定性与时间复杂度概述 在计算机科学中，排序算法是基础且重要的组成部分，用于将一系列数据按照特定顺序排列。排序算法的效率通常由其时间复杂度决定...
综上所述，根号n段归并排序算法通过分段和自底向上的合并策略，实现了线性平均时间复杂度，但在某些特定情况下可能表现出较差的性能。理解其工作原理和时间复杂度分析有助于我们在实际应用中选择合适的排序算法。
算法时间复杂度的计算 算法时间复杂度的计算是计算机科学中一个非常重要的概念，它描述了算法执行时间随着输入规模的变化而增长的速度。时间复杂度通常用大 O 记法表示，即 O(f(n))，其中 f(n) 是问题规模 n 的函数...
改进的堆排序算法及其复杂度分析改进的堆排序算法及其复杂度分析改进的堆排序算法及其复杂度分析改进的堆排序算法及其复杂度分析
- **评估可行性**：对于大规模数据处理问题，只有时间复杂度足够低的算法才具有实际应用价值。 - **优化设计**：了解时间复杂度可以帮助程序员在设计算法时避免使用低效的方法。 ### 5. 实际应用案例 例如，在开发...
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
### 算法的时间复杂度与空间复杂度详解 #### 一、算法复杂度概述 在计算机科学领域，算法的时间复杂度与空间复杂度是衡量一个算法效率的重要指标。时间复杂度关注的是算法执行时间的增长速率，而空间复杂度则侧重...
常用排序算法时间复杂度、空间复杂度总结。包括：冒泡排序、快速排序、选择排序、堆排序、插入排序、Shell排序、归并排序、基数排序。
本文将深入探讨五种常见的排序算法：堆排序、归并排序、选择排序、快速排序以及插入排序，并分析它们在不同数组状态下的时间复杂度。 1. **堆排序**： 堆排序是一种基于比较的排序算法，它利用了完全二叉树的特性...
1. 桶内排序的时间复杂度：如果每个桶都使用插入排序，那么每个桶的时间复杂度为O((n/k)²)，因为插入排序在最坏情况下需要O(n²)的时间。所以，所有桶的总时间复杂度为O(k * (n/k)²) = O(n²/k)。 2. 合并桶的...
在实际应用中，我们需要根据数据特点、内存限制以及对稳定性的需求选择合适的排序算法。例如，对于小规模数据，简单的排序算法如冒泡或插入排序可能是可行的；对于大规模数据，快速排序和归并排序等更高效。同时，...
然而，递归算法在提供简洁性和直观性的同时，也往往伴随着较高的时间和空间复杂度，尤其是当递归层数较深时，这种复杂度的增加可能会变得不可忽视。 ### 时间复杂度的概念 时间复杂度是衡量算法效率的重要指标之一...
"算法时间复杂度分析基础" 本文论述了算法时间复杂度分析的基础内容，涵盖了时间复杂度的定义、数学意义、分析示例等方面的知识点。 时间复杂度是指算法执行时间随输入规模增长而增长的量级，是评价算法优劣的重要...
Python 算法 09选择排序_时间复杂度_稳定性.mp4
### 快速排序改进算法：时间复杂度的深入解析 #### 快速排序的基本概念与问题 快速排序，由C.A.R.Hoare于1962年提出，是一种高效的排序算法，基于分治策略。它通过选择一个“基准”元素，将数据集分割成两个子集，...
使用插入、冒泡、选择、快排、归并、堆排共6种排序算法对同一序列进行排序，统计排序所需的平均时间并比较算法在时间上的优劣。供学习使用。
它能在O(n log n)的时间复杂度内完成排序，但不是稳定的排序算法。 时间对比部分可能包含这些排序算法在不同输入规模下的运行时间，帮助我们理解它们的实际性能差异。时间复杂度直线拟合则是一种统计方法，用于分析...