本文目录
- 数据结构中各种排序的时间复杂度与空间复杂度比较！
- 各种排序法的时间复杂度到底多少
- 排序算法的时间复杂度计算
- C语言 各常见排序法的时间复杂度 急 请简单说明
数据结构中各种排序的时间复杂度与空间复杂度比较！
冒泡排序是稳定的，算法时间复杂度是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) √ 0 顺序查找， 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)
各种排序法的时间复杂度到底多少
根据《算法导论（中文版）》P83表格以及《算法（中文版）》部分章节内容：
算法 最坏情况运行时间 平均情况
冒泡&&插入&&选择 排序 n^2 n^2
快速排序 n^2 n*log n
希尔排序（希尔增量） n^2 n^(1.3 - 2)
堆排序 n*log n n*log n
注：希尔排序的性能依赖于选择的增量。
排序算法的时间复杂度计算
你这个问题是自己想出来的吧？第一，你指的时间复杂度是大O表示法的复杂度，也就是一个上界，但不是上确界，所以就算你以一种方式中断排序过程，时间复杂度还是O(N*logN)，假设排序过程还能执行的话。第二，达到O(N*logN)的排序算法，以快速排序为例，快速排序不知道你看过没有，它不像选择排序或者冒泡排序那样，每一趟可以确定一直最大或者最小值，对于快速排序，每一趟排序后如果你删掉最后一个元素将导致整个算法失效。如果你要用这种删除元素方法的话，只能采用冒泡排序或者选择排序，时间复杂度是O(N^2)所以，我猜想你是不是想做类似于在N个元素中寻找前K个最大者之类的事情（K=N-L）如果是这样的话，有复杂度是O(N*logK)的算法，利用快速排序中的partition操作经过partition后，pivot左边的序列sa都大于pivot右边的序列sb；如果|sa|==K或者|sa|==K-1，则数组的前K个元素就是最大的前K个元素，算法终止;如果|sa|《K-1，则从sb中寻找前K-|sa|-1大的元素;如果|sa|》K，则从sa中寻找前K大的元素。一次partition(arr,begin,end)操作的复杂度为end-begin，也就是O(N)，最坏情况下一次partition操作只找到第1大的那个元素，则需要进行K次partition操作，总的复杂度为O(N*K)。平均情况下每次partition都把序列均分两半，需要logK次partition操作，总的复杂度为O(N*logK)。由于K的上界是N，所以以N表示的总复杂度还是O(N*logN)
C语言 各常见排序法的时间复杂度 急 请简单说明
选择排序算法复杂度是O(n^2)。插入排序是O(n^2)快速排序快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n^2)。堆排序算法时间复杂度O(nlogn)。归并排序的时间复杂度是O(nlog2n)。