各种排序算法的时间复杂度（各种排序算法的时间复杂度计算）

本篇文章给大家谈谈各种排序算法的时间复杂度，以及各种排序算法的时间复杂度计算对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、数据结构中排序和查找各种时间复杂度
• 2、快速排序法的平均时间复杂度和最坏时间复杂度分别是多少？
• 3、排序算法的时间复杂度

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

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

(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

(2)选择排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的。…… 例子说明好多了。序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了， 所以选择排序不稳定的排序算法

(3)插入排序

插入排序是在一个已经有序的小序列的基础上，一举坦亮次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果和插入元素相等，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变。所以插入排序是稳定的。

(4)快速排序

快速排序有两个方向，左边的i下标一直往右走（往后），当a[i] = a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走（往前），当a[j] a[center_index]。如果i和j都走不动了，i = j, 交换a[i]和a[j],重复上面的过程，直到ij。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法。（不稳定发生在中枢元素和a[j]交换的时刻）

(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) 1s2 不稳定???="" 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）

[img]

快速排序法的平均时间复杂度和最坏时间复杂度分别是多少？

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

当排序已经成为基本有序携隐状态时，快速排序退化为O(n^2)，一般情况下，排序为指数复杂度。

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

扩展资料

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序，它采用了一种分治的策略，通常称其为分治法。快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

（1）首先设定一个分界值，通过该分界值将数组分成左右两部分。

（2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

（3）然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

（4）重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

排序算法的时间复杂度

时间复杂度：即扮郑从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。

时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐进的，亦即考察输入值大小趋近无穷时的情况。

扩展资料

所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的逗搜规则，体现出一定的规律，因此，经处理后的数据便于筛选和山缺历计算，大大提高了计算效率。

对于排序，我们首先要求其具有一定的稳定性，即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的，不允许混淆不清。

参考资料来源：百度百科-排序算法

参考资料来源：百度百科-时间复杂性

关于各种排序算法的时间复杂度和各种排序算法的时间复杂度计算的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。