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

每种查找方法的时间复杂度~

1、首先，先打开DEV C++软件，然后点击“新建源代码”，或者直接按住键盘上的Ctrl+n进行新建源代码。

2、新建好文件项目之后，在编辑页面输入以下代码。

3、代码编写完成之后，点击“运行”，即菜单栏上的第二个四色块正方形的按钮进行运行，或者直接按键盘上的F11进行编译运行。

4、运行之后，即可看到这次程序代码要实现的算法效果了。

5、因为面积可能存在小数点，但是在编写代码时，使用的是int整数类型，所以最后得到的结果是不带小数点的整数，大家可以根据自己的要求改为浮点型：float，然后输出时改为：%s 即可。

6、时间复杂度其实是和代码算法有关系的，第一是看循环次数，再看是否有循环倍数关系，如果以上情况都不存在，则时间复杂度都是：O（1）。在算法代码中计算时间复杂度。由上述的代码算法得出其时间复杂度为：O（1）。

冒泡排序是这样实现的：

首先将所有待排序的数字放入工作列表中。

从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。

重复2号步骤，直至再也不能交换。

冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。

选择排序

选择排序是这样实现的：

设数组内存放了n个待排数字，数组下标从1开始，到n结束。

i=1

从数组的第i个元素开始到第n个元素，寻找最小的元素。

将上一步找到的最小元素和第i位元素交换。

如果i=n－1算法结束，否则回到第3步

选择排序的平均时间复杂度也是O(n^2)的。

冒泡排序是稳定的，算法时间复杂度是O(n ^2)。

2.2 选择排序（Selection Sort）

选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。

选择排序是不稳定的，算法复杂度是O(n ^2 )。

2.3 插入排序 （Insertion Sort）

插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i] 又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。

直接插入排序是稳定的，算法时间复杂度是O(n ^2) 。

2.4 堆排序

堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

堆排序是不稳定的，算法时间复杂度O(nlog n)。

2.5 归并排序

设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。

其时间复杂度无论是在最好情况下还是在最坏情况下均是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)
√

顺序查找， O(n)
二分， O(logn)需要排序
分块 分块查找？ 不知道..英文是什么？

直接插入 O(n^2)
快速排序 最坏情况O(n^2) 平均O(nlogn)
起泡 和插入很像吧 O(n^2)
希尔，O(n^x) 1<x<2 需要比较复杂的分析方法
选择 没听过
堆排序 最坏情况和平均都是O(nlogn)

其他：
归并(merge) O(nlogn)
radix() （看怎么来理解n，也可以说O(n)也可以O(nlogn),需要调用稳定的子排序算法）
basket O(n) 这两个属于非比较排序。

给予比较操作（> 或< ）的排序算法理论最低复杂度是O(nlogn)
证明： 所有可能情况为n!
构造决策树需要n!子节点 <为二分操作，所以树为二叉树，高度为O(logn!)=O(nlogn)

算法用英文倒不是我崇洋媚外 只是从大学才开始学，而我们学校的教科书都是英语的.

排序算法的稳定性和算法的具体实现有关 通常认为不稳定的快排也有一些小技巧让他稳定

---

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

奇台县18889839513： C语言 各常见排序法的时间复杂度 急 请简单说明 - ？
崔博晴达： 选择排序抄算法复杂度是O(n^2). 插入排序是O(n^2) 快速排序快速排序是不稳2113定的.5261最理想情况算法时间复杂度O(nlog2n),最坏4102O(n^2). 堆排序算法时间复杂度O(nlogn). 归并1653排序的时间复杂度是O(nlog2n).

奇台县18889839513： 快速排序法的平均时间复杂度和最坏时间复杂度分别是多少? - ？
崔博晴达： 快速排序的平均时间复杂度和最坏时间复杂度分别是O(nlgn)、O(n^2). 当排序已经成为基本有序状态时,快速排序退化为O(n^2),一般情况下,排序为指数复杂度. 快速排序最差情况递归调用栈高度O(n),平均情况递归调用栈高度O(logn),而...

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

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

奇台县18889839513： 什么是C语言中的时间复杂度?如何计算? - ？
崔博晴达： 时间复杂度不是相对于程序而言的,而是指问题的复杂 例如排序,对分查找在最劣情况下也是平方问题,但对于绝大多数问题而言,我们只关心平均效率. 例如稀疏数组,可以降低对空间的要求,但当有用数据超过一定规模,运行速度将急剧下降. 次数超过4的多项式没有平凡解,所以被成为大O的N次方问题,这样的问题总是需要那么多时间才能完成计算,这就是时间的复杂度. 任何数据的压缩都有极限,越是随机的数据,越不能找到良好的数据结构,这就是空间的复杂性. 实际上如果没有好的算法和数据结构,大多数程序是无法真正做到应用的.

奇台县18889839513： 列举两种排序方式,并写出时间复杂度 - ？
崔博晴达： 常见排序方法:插入、交换、选择、合并等等.交换排序包含冒泡排序和快速排序.选择排序包含shaker排序和堆排序. 插入排序和冒泡排序又被称作简单排序,他们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平.基数排序是针对关键字在一个较小范围内的排序算法.

奇台县18889839513： 时间复杂度 - ？
崔博晴达： for(i=0;i<n;i++)for(j=0;j<i;j++) 需要计算的i,j值分别为i=0 i=1 j=0 i=2 j=0 1 ... i=n j=0 1 2 3 ... n-1 一共是 1+2+3+...n-1 = (n^2-n)/2, 所以,两层for下的时间复杂度是o(n^2)三次的时候i=0 i=1 (1^2 - 1)/2 因为这是一个n=1的两层循环 i=2 (2^2 - 2)/2 ....

奇台县18889839513： 怎么估算c语言冒泡排序法的时间复杂度 - ？
崔博晴达： 冒泡排序的算法时间复杂度上O(n^2 )冒泡排序是这样实现的:首先将所有待排序的数字放入工作列表中.从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换.重复2号步骤,直至再也不能交换.冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法.选择排序选择排序是这样实现的:设数组内存放了n个待排数字,数组下标从1开始,到n结束.i=1从数组的第i个元素开始到第n个元素,寻找最小的元素.将上一步找到的最小元素和第i位元素交换.如果i=n-1算法结束,否则回到第3步选择排序的平均时间复杂度也是O(n^2)的.