排序算法的时间复杂度

冒泡排序算法的时间复杂度是什么?~

初始状态是正序的，一趟扫描即可完成排序，所需的关键字比较次数和记录移动次数均达到最小值：

冒泡排序就是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。
所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
扩展资料：
冒泡排序算法的原理如下：
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
参考资料来源：百度百科-冒泡排序

在冒泡排序，插入排序，选择排序，快速排序中，在最最坏情况下，快速排序的时间复杂为O(n2) ，插入排序O(n2)，选择排序O(n2)，冒泡排序O(n2)。所以ABCD时间复杂度是一样的。

知识拓展：在快速排序算法中，最为关键的就是选取一个基值，将数组分为大于基值以及小于基值两部分，并返回基值所以在位置以利用于递归划分。
对数组a，设需要划分的其中一段为a[p]~a[r]，我们期待的结果是得到一个q，其中p<=q<=r，使得a[p]~a[q-1]<=a[q]<=a[q+1]~a[r]，这个时候原先的一段数组被分成了三部分。
首先，设基值为这段数组的最后一个元素a[r]，我们希望最后得到的结果是a[r]现在对应的值在算法结束后可以排在比他大和小的两部分的中间爱。
然后令i=p-1; j=p，当发现有a[j]>x时，j继续前进，不需要任何移动。当发现a[j]<=x时，我们需要将这个元素放到小于基值的一边，于是将i自加1，并交换此时a[i]，与a[j]的元素，然后j自加1。这个时候i指向的是比基值小的那段数据的最后一个元素，j指向的是第一个还没有判断的剩余元素。
上面一步不断循环直到j指向了r，此时只剩下r没有和基值判断了，而a[r]本来就是基值，而除了a[r]以外，a[p]~a[i]是小于基值的部分，a[i+1]~a[r-1]是大于基值的部分，所以此时只需交换a[i+1]和a[r]即可。
由于对数组a从头到尾扫描一次就可以得到结果，因此这一部分算法复杂度为o(n)

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

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

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

扩展资料

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

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

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

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

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。

一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。

而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

扩展资料：

排序算法经过了很长时间的演变，产生了很多种不同的方法。对于初学者来说，对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合，很难通用。因此，我们很有必要对所有常见的排序算法进行归纳。

排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。

内排序有可以分为以下几类：

(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。

(2)、选择排序：直接选择排序、堆排序。

(3)、交换排序：冒泡排序、快速排序。

(4)、归并排序

(5)、基数排序

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

百度百科-空间复杂度

---

张湾区19494971246： C语言 各常见排序法的时间复杂度 急 请简单说明 - ？
白璧地力： 选择排序抄算法复杂度是O(n^2). 插入排序是O(n^2) 快速排序快速排序是不稳2113定的.5261最理想情况算法时间复杂度O(nlog2n),最坏4102O(n^2). 堆排序算法时间复杂度O(nlogn). 归并1653排序的时间复杂度是O(nlog2n).

张湾区19494971246： 冒泡排序时间复杂度冒泡排序最好的时间复杂度为 - ________,平均时间复杂度为 - _______ -- ？
白璧地力：[答案] 冒泡排序的最坏时间复杂度为O(n2). 算法的平均时间复杂度为O(n2) .冒泡排序最好的时间复杂度为O(n).

张湾区19494971246： 什么是算法的时间复杂度排序. - ？
白璧地力： 算法复杂度分两种:一、时间复杂度 二、空间复杂度 你这里说的应该指的是时间复杂度.时间复杂度的计算需要一定的经验.可以参考这里:http://baike.baidu.com/view/104946.htm

张湾区19494971246： 什么排序的速度(时间复杂度)最快? - ？
白璧地力： 从时间复杂度看,所有内部排序方法可以分为两类.1.插入排序 选择排序 起泡排序 其时间复杂度为O(n2);2.堆排序 快速排序 归并排序 其时间复杂度为O(nlog2n).这是就平均情况而言的,如果从最好的情况考虑, 则插入排序和起泡排序的时间复杂度最好,为O(n), 而其他算法的最好情况同平均情况大致相同.如果从最坏的情况考虑,快速排序的时间复杂度为O(n2),插入排序和起泡排序虽然同平均情况相同,但系数大约增加一倍,运行速度降低一半,而选择排序、堆排序和归并排序则影响不大.总之, 在平均情况下,快速排序最快; 在最好情况下,插入排序和起泡排序最快; 在最坏情况下,堆排序和归并排序最快.

张湾区19494971246： 请问一下:有谁能总结数据结构中排序章内介绍各种算法的时间复杂度呀,很急... - ？
白璧地力： 1.插入排序:每次将一个待排的记录插入到前面的已经排好的队列中的适当位置.①.直接插入排序 直接排序法在最好情况下(待排序列已按关键码有序),每趟排序只需作1次比较而不需要移动元素.所以n个元素比较次数为n-1,移动次数0....

张湾区19494971246： 选择排序的时间复杂度问题 - ？
白璧地力： 排序的基本操作为比较和移动,算法的时间复杂度主要考虑基本操作的频度,选择排序主要时间花在比较上,所以时间复杂度为O(n^2)

张湾区19494971246： 排序里的时间复杂度o是什么意思? - ？
白璧地力： T(n)=O(f(n)) T由O和F复合得到,F是问题规模到原操作频数的映射,O是频数到时间的映射!

张湾区19494971246： 快速排序时间复杂度怎样推算的 - ？
白璧地力： 快速排序是基于二分的,所以在理想情况下它的时间复杂度为O(NLOG2N),极端情况下(数据恰好逆序)则相当于选择排序,复杂度退化为O(N^2);

张湾区19494971246： 求各种查找和排序的时间复杂度 - ？
白璧地力： 冒泡排序是稳定的,算法时间复杂度是O(n ^2). 2.2 选择排序(Selection Sort) 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置.这样,经过i遍处理之后,前i个记录的位置已经是正确...