排序算法时间复杂度口诀（C语言 各常见排序法的时间复杂度 急 请简单说明）

本文目录

• C语言 各常见排序法的时间复杂度 急 请简单说明
• 几种排序的时间复杂度排序
• 时间复杂度和排序方法
• 快速排序时间复杂度
• 常见排序算法以及对应的时间复杂度和空间复杂度
• 数据结构中排序和查找各种时间复杂度
• 快速排序算法在平均情况下的时间复杂度为 求详解
• 求各种查找和排序的时间复杂度

C语言 各常见排序法的时间复杂度 急 请简单说明

选择排序算法复杂度是O(n^2)。
插入排序是O(n^2)
快速排序快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n^2)。
堆排序算法时间复杂度O(nlogn)。
归并排序的时间复杂度是O(nlog2n)。

几种排序的时间复杂度排序

从时间复杂度看，bai所有内部排序du方法可以分为两类。zhi
1.插入排序 选择排序 起泡排序
其时dao间复杂度为O(n2)；
2.堆排序 快速排序 归并排序
其时间复杂度为O(nlog2n)。
这是就平均情况而言的，如果从最好的情况考虑，
则插入排序和起泡排序的时间复杂度最好，为O(n)，
而其他算法的最好情况同平均情况大致相同。
如果从最坏的情况考虑，快速排序的时间复杂度为O(n2)，插入排序和起泡排序虽然同平均情况相同，但系数大约增加一倍，运行速度降低一半，而选择排序、堆排序和归并排序则影响不大。

时间复杂度和排序方法

一个算法流程中 ， 常熟操作数量的指标， 这个指标叫做 O， 如果常熟的操作数量表达式中只要高阶项，不要低阶项， 也不要高阶项的系数，剩下的部分记为(fn), 那么时间复杂度就是O（fn）

一种最简单的方法是循环：

另一种方法是采用的二分法：
注意因为这是一个有序的数组， 所以我们可以先分一半, 然后比较我们要寻找的数字是是在左边的数组还是右边的数组，如果在左边将左边的数组一分为二， 然后继续划分。

第一种方法的时间复杂度是O(n), 第二种方法的时间复杂度是 O(logN)可以看出对于一个有序数组数量比较多的时候，二分法确实比较优秀一点。

第一种方法是直接两个数组分别循环找到其中的相同部分。 时间复杂度是 O(n*m)

第二种方法是：
对arr1数组进行循环， 然后在arr2中用二分去查找， 时间复杂度是O(n*logm)

第三种方法是 ， 如果左边数组比右边的数组小的话 就将左边的数组进行移动 ， 如果左边比右边大的话 ， 就将右边的数组进行移动 ， 如果两个相等的话就共同移动。其中的时间复杂度是O(n+m); 加上continue之后速度快了很多。

介绍完时间复杂度之后我们来看看几种排序方法。

所谓的冒泡排序就是先将最后一位固定最大的或者是最小的，然后取固定到倒数第二位中去固定， 我们如果对他进行使用冒泡从小到大开始排序的话应该怎么做呢？
首先排从第一个数字开始排序， 如果当前数字比下一个数字小或者相等的话，那么指针后移，在继续比较下一位，如果是当前数字大于下一位的话就会发生交换，然后指针向后移动。直到最大数字成为最后一位。
整个的时间复杂度是n-1+ n-2+...1

下面介绍一下对数器，所谓的对数器就用你所知道的简单的算法去验证下当前缩写算法的正确性。
我们平时写的算法可以用对数器来验证下

插入算法的精髓是，外部循环保证从1 的时候， 左边的数组是有序的， 如果是左边的数组没有顺序的，就内部循环发生交换， 比如说我们现在有一个数组是let arr = ，我们要保证他从小到大进行排序
外部循环从1开始， 左边的数组是 , 然后还是内部循环进行调序， 以此类推，最后的时间复杂度是2+3+4+...n-1

快速排序时间复杂度

快速排序的平均时间复杂度和最坏时间复杂度分别是O(nlgn)、O(n^2)。

快速排序最差情况递归调用栈高度O(n)，平均情况递归调用栈高度O(logn)，而不管哪种情况栈的每一层处理时间都是O(n)，所以，平均情况（最佳情况也是平均情况）的时间复杂度O(nlogn)，最差情况的时间复杂度为O(n^2)。

评价标准：

稳定性是一个特别重要的评估标准。稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序，这是我们不愿意看到的。

我们在使用排序算法或者选择排序算法时，更希望这个次序不会改变，更加稳定，所以排序算法的稳定性，是一个特别重要的参数衡量指标依据。就如同空间复杂度和时间复杂度一样，有时候甚至比时间复杂度、空间复杂度更重要一些。

常见排序算法以及对应的时间复杂度和空间复杂度

排序 ：将杂乱无章的数据，按照一定的方法进行排列的过程叫做排序。

排序大的分类可分为 内排序 和 外排序 ，不需要访问外存就能进行排序的叫做内排序。

排序也可以分为 稳定排序 和 不稳定排序

稳定排序 ：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。即；若 a , a 在 a 之前，经过排序后 a 依然在 a 之前。冒泡排序、直接插入排序、二分插入排序、归并排序，基数排序都是稳定排序。
不稳定排序 ：直接选择排序、堆排序、快速排序、希尔排序，猴子排序。

以升序为例，比较相邻的元素，如果第一个比第二个大，则交换他们两个。如果两个元素一样大，则继续比较下一对。所以冒泡排序是一种稳定排序。

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。快速排序是不稳定排序。

将序列分为两个部分{{有序序列},{无序}}，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。如果碰到相等的元素，就会把它插入到想等元素后面，顺序不会改变，所以直接插入排序是稳定排序。

在直接插入排序的基础上，对有序序列进行划分。例如：序列为 {{a} 其中 {a} 为有序序列，取 a ，将其与 a 比较，即可确定 a 的范围 (a 或者 a) ,然后继续在已确定的范围内进行二分。范围依次缩小为： 1/2、1/4、1/8、1/16...... 可快速确定a应该插入的位置。二分插入排序也是稳定排序。

将整个序列分割成若干个小的子序列，每个子序列内分别进行插入排序。一般情况下步长取n/2。直到最后一次步长为1，即所有元素在一个组中进行排序。由于希尔排序是先将整个序列划分为多个子序列进行排序，相同的元素顺序在这个过程中顺序可能会被打乱，所以希尔排序是不稳定排序。

从待排序的数据元素中，选出最小或最大的元素与序列第一个数交换。直到所有数据排完。直接选择排序是不稳定排序。例如： {3，3，1} ，第一次排序就将1和第一个3交换，想等元素的顺序改变了。

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

堆排序是一种树形选择排序，是对直接选择排序的有效改进。
最大堆:每个节点的值都大于等于它的孩子节点。
最小堆:每个节点的值都小于等于它的孩子节点。
最大堆第0个数据是最大数，最小堆第0个数据是最小数。
堆排序是不稳定排序

思想

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
如何将两个有序序列合并？(升序)
{a}
若 b ，取 b 放入数组 c 中，然后继续比较数组 a 和 b 中的第一个元素，直到数组 a 和 b 中最后一对元素比较完成。

思想

将数组分成二组 a , b 如果这二组组内的数据都是有序的，那么就可以按照上述方法对这二组数据进行排序。如果这二组数据是无序的？
可以将 a , b 组各自再分成二组。递归操作，直到每个小组只有一个数据，每个小组只有一个元素所以我们可以认为它已经是有序序列，然后进行合并。
先分解后合并。
归并排序是稳定排序

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。从最低位起从0-9依次扫描序列，一边扫描一边将扫描到的数据加到新的序列中，得到一个序列。然后比较高一位，重复上述操作，直到最高位排序完成。数列就变成一个有序序列。基数排序是稳定排序。

以全是二位数的序列举例

无限猴子定理 :指一只猴子随机在打字机键盘上按键，最后必然可以打出法国国家图书馆的每本图书。

时间复杂度最低1次，最高可执行到世界的尽头。。。

数据结构中排序和查找各种时间复杂度

数据结构中排序和查找各种时间复杂度
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
(2)选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的。…… 例子说明好多了。序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了， 所以选择排序不稳定的排序算法
(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果和插入元素相等，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变。所以插入排序是稳定的。
(4)快速排序
快速排序有两个方向，左边的i下标一直往右走（往后），当a交换的时刻）
(5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列。不断合并直到原序列全部排好序。相等时不发生交换。所以，归并排序也是稳定的排序算法。
(6)基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
(8)堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序是不稳定的排序算法
一、排序
排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2) O(n2) 稳定 O(1) n小时较好
交换 O(n2) O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
Shell O(nlogn) O(ns) 1《s《2 不稳定???="" o(1)???????="" s是所选分组《/s
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好
基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9)，R是基数(个十百)
二、查找
未写……
三 树图
克鲁斯卡尔算法的时间复杂度为O（eloge）
普里姆算法的时间复杂度为O（n2）
迪杰斯特拉算法的时间复杂度为O（n2）
拓扑排序算法的时间复杂度为O（n+e）
关键路径算法的时间复杂度为O（n+e）

快速排序算法在平均情况下的时间复杂度为 求详解

时间复杂度为O(nlogn) n为元素个数
1. 快速排序的三个步骤：
1.1. 找到序列中用于划分序列的元素
1.2. 用元素划分序列
1.3. 对划分后的两个序列重复1,2两个步骤指导序列无法再划分
所以对于n个元素其排序时间为
T(n) = 2*T(n/2) + n （表示将长度为n的序列划分为两个子序列，每个子序列需要T(n/2)
的时间，而划分序列需要n的时间）
而 T(1) = 1 （表示长度为1的序列无法划分子序列，只需要1的时间即可）
T(n) = 2^logn + logn * n （n被不断二分最终只能二分logn次（最优的情况,每次选取
的元素都均分序列））
= n + nlogn
因此T(n) = O(nlogn)
以上是最优情况的推导，因此快速排序在最优情况下其排序时间为O(nlogn),通常平均情况
我们也认为是此值。
在最坏情况下其会退化为冒泡排序，T(n) = T(n - 1) + n (每次选取的元素只能将序列划分为
一段，即自身是 最小元素或最大元素)
因此T(n) = n * (n-1) / 2 相当于O(n^2)

求各种查找和排序的时间复杂度

冒泡排序是稳定的，算法时间复杂度是O(n ^2)。
2.2 选择排序（Selection Sort）
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
选择排序是不稳定的，算法复杂度是O(n ^2 )。
2.3 插入排序 （Insertion Sort）
插入排序的基本思想是，经过i-1遍处理后,L时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。
直接插入排序是稳定的，算法时间复杂度是O(n ^2) 。
2.4 堆排序
堆排序是一种树形选择排序，在排序过程中，将A看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
堆排序是不稳定的，算法时间复杂度O(nlog n)。
2.5 归并排序
设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A。
其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。
2.6 快速排序
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
快速排序是不稳定的，最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。
2.7 希尔排序
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为 增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
希尔排序是不稳定的，其时间复杂度为O(n ^2)。
排序类别
时间复杂度
空间复杂度
稳定

1
插入排序
O(n2)
1
√

2
希尔排序
O(n2)
1
×

3
冒泡排序
O(n2)
1
√

4
选择排序
O(n2)
1
×

5
快速排序
O(Nlogn)
O(logn)
×

6
堆排序
O(Nlogn)
1
×

7
归并排序
O(Nlogn)
O(n)
√