1楼：q给你毛起
关键字比较次数永远是n(n-1)/2，记录移动次数最多为3(n-1)，最少0次，前者起主导作用，因此实际上时间复杂度还是o(n^2)。
在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数c=(n*n - n)/2,总的移动次数 3(n-1).由此可知，直接选择排序的时间复杂度为 o(n2) 。
以下排序算法最坏情况下时间复杂度最低的是 a.冒泡排序 b.插入 c.选择 d.快排
2楼：木头释然
在冒泡排序，插入排序，选择排序，快速排序中，在最最坏情况下，快速排序的时间复杂为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)
3楼：匿名用户
1.选择排序：不稳定，时间复杂度 o(n^2)
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将l[i..n]中最小者与l[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
2.插入排序：稳定，时间复杂度 o(n^2)
插入排序的基本思想是，经过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)三次插入。
3.冒泡排序：稳定，时间复杂度 o(n^2)
冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。
所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。
在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
4.堆排序：不稳定，时间复杂度 o(nlog n)
堆排序是一种树形选择排序，在排序过程中，将a[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
5.归并排序：稳定，时间复杂度 o(nlog n)
设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为a[l..m]，a[m+1..h]，将它们归并为一个有序数列，并存储在a[l..h]。
6.快速排序：不稳定，时间复杂度 最理想 o(nlogn) 最差时间o(n^2)
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。
快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
几种排序的时间复杂度，可以参考一下
4楼：匿名用户
这几个的最坏情况下的时间复杂度都是一样的，一定要比较的话快排比较快，但冒泡排序比较稳定，最坏的话都是一样的
5楼：匿名用户
显然都一样，如果论平均时间就是快排最快o(nlogn)，其余的都是o(n^2)，但快排最坏时间也是o(n^2)
6楼：匿名用户
最坏的情况下好像都是n^2吧。
排序算法zui最好情况下时间复杂度为n的算法有哪些
7楼：1554又来了
理论上只有计数排序。
开一个数组a
每读一个数字x，那么a[x]就加一
例如读入4那么a[4]就加1，最后再遍历一边。
快速排序算法在平均情况下的时间复杂度为 求详解
8楼：匿名用户
时间复杂度为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)
9楼：匿名用户
时间复杂度为o（nlogn）n是多少元素
1。快速排序的三个步骤：
1.1。查找序列用于划分的序列中的元素
1.2元素划分的序列
1.3 1,2两个步骤的过程不断重复，两个序列划分指导序列不能被细分
n个元素的排序条件为t（n）= 2 * t（n / 2个）+ n（表示序列分为两个子序列中的n的长度，每个子序列需要到t（n / 2个）
时间除以
t（1）= 1（序列的长度不能被划分为子序列，序列的n个）只需要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）
10楼：雨的恩惠
正如归并排序一样，快速排序也是递归的，因此，他的分析需要求解一个递推公式。我们将对快速排序进行这种分析，假设有一个随机的枢纽元（不用三数中值分割法），对一些小的文件也不使用截止范围。和归并排序一样，取t(0)=t(1)=1,快速排序的运行时间等于两个递归调用的运行时间加上花费在分割上的限行时间（枢纽元的选取仅花费常数时间）。
我们得到基本的快速排序关系：
t(n)=t(i)+t(n-i-1)+**
其中，i=|s1|是s1中的时间个数。我们还将考查三种情况。
最坏情况的分析：
枢纽元始终是最小元素。此时i=0，如果我们忽略无关紧要的 t(0)-1,那么递推关系为
t(n0=t(1)+c(sum+=i;i in (2,n])= o(n^2)
最好情况：
在最好的情况下，枢纽元正好位于中间，t(n)=o(n* log(n))
平均情况的分析：
t(n)=o(n*logn)
《数据结构与算法分许（c语言描述）》 片段，字太多了，全是公式推导，打了一部分
11楼：郝霞佛念
快速排序时间复杂度下界为o(nlogn)，最坏情况为o(n^2)
快速排序的平均时间复杂度为o(nlogn)。
下列排序算法中，不受数据初始状态影响，时间复杂度为o(n*logn)的是
12楼：匿名用户
a。（在堆
bai排序和快速排序中du，若原始记录接近正zhi序或反序，则选用dao_堆排序____，若专原始记录无序，则最属好选用__快速排序___。）
c错了。c的原题是下列排序法中，时间复杂度不收数据初始状态影响，总是为o(n2）的是__直接选择排序 ____。
13楼：匿名用户
选a。bcd最差情况是o(n^2);
14楼：匿名用户
o(n*logn)这个是什么意思!
在各类算法中那种算法排序是最快的？
15楼：crazy不痛
说句实话，没有最快
这一说。
如果不在乎浪费空间，应该是桶排序最快
如果整体基本有序，插入排序最快
如果考虑综合情况，快速排序更加实用常见（希尔排序、堆排序等各种排序也各有优劣）
一般情况下，冒泡这种排序仅仅是名字起的有趣罢了，不太好用
16楼：树袋熊刘
直接插入排序：当数据有序时，执行效率最好，此时的时间复杂度为o(n)；当数据基本反序时，执行效率最差，此时的时间复杂度为o(n2)。所以当数据越接近有序，直接插入排序算法的性能越好。
希尔排序 ：时间效率为o(n(log2n)2)
直接选择排序：时间效率为 o(n^2)——虽移动次数较少，但比较次数仍多。
堆排序：时间效率为o(nlog2n)
冒泡排序：时间效率为o（n^2) —因为要考虑最坏情况（数据元素全部逆序），当然最好情况是数据元素已全部排好序，此时循环n-1次，时间复杂度为o（n)
快速排序：
时间效率：一般情况下时间复杂度为o(nlog2n)，最坏情况是数据元素已全部正序或反序有序，此时每次标准元素都把当前数组分成一个大小比当前数组小1的子数组，此时时间复杂度为o(n2)
各种排序法的时间复杂度到底多少,各种排序法的时间复杂度到底多少 10
1楼 世界文明导师 根据《算法导论 中文版 》p83 以及《算法 中文版 》部分章节版内容 算法 最坏情况运行时权间 平均情况 冒泡 插入 选择 排序 n 2 n 2 快速排序 n 2 n log n 希尔排序 希尔增量 n 2 n 1 3 2 堆排序 n log n n log n 注 希尔排序的...