《数据结构时间复杂度总汇》由会员分享，可在线阅读，更多相关《数据结构时间复杂度总汇（3页珍藏版）》请在金锄头文库上搜索。
1、(1) 冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。(2) 选择排序选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的。例子说明好多了。序列58529，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不稳定的排序算法。(3) 插入排序插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，
2、否则一直往前找直到找到它该插入的位置。如果和插入元素相等，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变。所以插入排序是稳定的。(4) 快速排序快速排序有两个方向，左边的i下标一直往右走(往后)，当aiacenter_index。如果i和j都走不动了，ij。交换aj和acenter_index，完成一趟快速排序。在中枢元素和aj交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为53343891011，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法。(不稳定发生在中枢元素和aj交换的时刻)归并
3、排序归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列。不断合并直到原序列全部排好序。相等时不发生交换。所以，归并排序也是稳定的排序算法。(5) 基数排序基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。(6) 希尔排序(shell)希尔排序是按照不同步长对元素进行插入排
4、序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(nA2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。(7) 堆排序我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最
5、大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1,n/2-2,1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序是不稳定的排序算法、排序排序法平均时间最差情形稳定度额外空间备注冒泡0(n2)0(n2)稳定0(1)n小时较好交换0(n2)0(n2)不稳定0(1)n小时较好选择0(n2)0(n2)不稳定0(1)n小时较好插入0(n2)0(n2)稳定0(1)大部分已排序时较好Shell0(nlogn)0(ns)
6、1s2不稳定0(1)s是所选分组快速0(nlogn)0(n2)不稳定0(nlogn)n大时较好归并0(nlogn)0(nlogn)稳定0(1)n大时较好堆0(nlogn)0(nlogn)不稳定0(1)n大时较好基数0(logrB)0(logrB)稳定0(n)B是真数(0-9)，R是基数(个十百)二、查找二分法平均查找效率是O(logn)，但是需要数组是排序的。如果没有排过序，就只好先用0(nlogn)的预处理为它排个序了。而且它的插入比较困难，经常需要移动整个数组，所以动态的情况下比较慢。哈希查找理想的插入和查找效率是0(1)，但条件是需要找到一个良好的散列函数，使得分配较为平均。另外，哈希表
7、需要较大的空间，至少要比0(n)大几倍，否则产生冲突的概率很高。二叉排序树查找也是O(logn)的，关键是插入值时需要做一些处理使得它较为平衡(否则容易出现轻重的不平衡，查找效率最坏会降到0(n),而且写起来稍微麻烦一些，具体的算法你可以随便找一本介绍数据结构的书看看。当然，如果你用的是c语言，直接利用它的库类型mapmultimap就可以了，它是用红黑树实现的，理论上插入、查找时间都是O(logn)，很方便，不过一般会比自己实现的二叉平衡树稍微慢一些。三树图克鲁斯卡尔算法的时间复杂度为0(eloge)普里姆算法的时间复杂度为0(n2)迪杰斯特拉算法的时间复杂度为0(n2)拓扑排序算法的时间复
8、杂度为0(n+e)关键路径算法的时间复杂度为0(n+e)8.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为(c)。A.O(n)B.O(1)C.O(log2n)D.O(n2)9.从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为(a)。A.O(n)B.O(1)C.O(log2n)D.O(n2)2.根据n个元素建立一棵二叉排序树，其时间复杂度大致为(b)2A.O(n)B.O(nlog2n)C.O(log2n)D.O(n)3设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储结构(即三元组存储结构)其转置矩阵的普通转置算法的时间复杂度为(d)A.O(m)B.O(n)C.O(n*m)D.O(m*t)E.O(n*t)欢迎您的下载，资料仅供参考!致力为企业和个人提供合同协议，策划案计划书，学习资料等等打造全网一站式需求
