十大排序算法时间复杂度,九大排序算法时间复杂度

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

冒泡排序是稳定的，算法时间复杂度是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)

√

常见排序算法以及对应的时间复杂度和空间复杂度

排序 ：将杂乱无章的数据，按照一定的方法进行排列的过程叫做排序。

排序大的分类可分为 内排序 和 外排序 ，不需要访问外存就能进行排序的叫做内排序。

排序也可以分为 稳定排序 和 不稳定排序

稳定排序 ：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。即；若 a[i]=a[j] , a[i] 在 a[j] 之前，经过排序后 a[i] 依然在 a[j] 之前。冒泡排序、直接插入排序、二分插入排序、归并排序，基数排序都是稳定排序。

不稳定排序 ：直接选择排序、堆排序、快速排序、希尔排序，猴子排序。

以升序为例，比较相邻的元素，如果第一个比第二个大，则交换他们两个。如果两个元素一样大，则继续比较下一对。所以冒泡排序是一种稳定排序。

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。快速排序是不稳定排序。

将序列分为两个部分{{有序序列},{无序}}，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。如果碰到相等的元素，就会把它插入到想等元素后面，顺序不会改变，所以直接插入排序是稳定排序。

在直接插入排序的基础上，对有序序列进行划分。例如：序列为 {{a[0]......a[i-1]},a[i]} 其中 {a[0]......a[i-1]} 为有序序列，取 a[(i-1)/2] ，将其与 a[i] 比较，即可确定 a[i] 的范围 (a[0]...a[(i-1)/2] 或者 a[(i-1)/2]...a[i-1]) ,然后继续在已确定的范围内进行二分。范围依次缩小为： 1/2、1/4、1/8、1/16...... 可快速确定a[i]应该插入的位置。二分插入排序也是稳定排序。

将整个序列分割成若干个小的子序列，每个子序列内分别进行插入排序。一般情况下步长取n/2。直到最后一次步长为1，即所有元素在一个组中进行排序。由于希尔排序是先将整个序列划分为多个子序列进行排序，相同的元素顺序在这个过程中顺序可能会被打乱，所以希尔排序是不稳定排序。

从待排序的数据元素中，选出最小或最大的元素与序列第一个数交换。直到所有数据排完。直接选择排序是不稳定排序。例如： {3，3，1} ，第一次排序就将1和第一个3交换，想等元素的顺序改变了。

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

最大堆:每个节点的值都大于等于它的孩子节点。

最小堆:每个节点的值都小于等于它的孩子节点。

最大堆第0个数据是最大数，最小堆第0个数据是最小数。

堆排序是不稳定排序

思想

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

如何将两个有序序列合并？(升序)

{a[0]......a[i-1]},{b[0]......b[j-1]}

若 b[0]a[0] ，取 b[0] 放入数组 c 中，然后继续比较数组 a 和 b 中的第一个元素，直到数组 a 和 b 中最后一对元素比较完成。

思想

将数组分成二组 a , b 如果这二组组内的数据都是有序的，那么就可以按照上述方法对这二组数据进行排序。如果这二组数据是无序的？

可以将 a , b 组各自再分成二组。递归操作，直到每个小组只有一个数据，每个小组只有一个元素所以我们可以认为它已经是有序序列，然后进行合并。

先分解后合并。

归并排序是稳定排序

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。从最低位起从0-9依次扫描序列，一边扫描一边将扫描到的数据加到新的序列中，得到一个序列。然后比较高一位，重复上述操作，直到最高位排序完成。数列就变成一个有序序列。基数排序是稳定排序。

以全是二位数的序列举例

无限猴子定理 :指一只猴子随机在打字机键盘上按键，最后必然可以打出法国国家图书馆的每本图书。

时间复杂度最低1次，最高可执行到世界的尽头。。。

快速排序法的平均时间复杂度和最坏时间复杂度分别是多少？

快速排序的平均时间复杂度和最坏时间复杂度分别是O(nlgn)、O(n^2)。

当排序已经成为基本有序状态时，快速排序退化为O(n^2)，一般情况下，排序为指数复杂度。

快速排序最差情况递归调用栈高度O(n)，平均情况递归调用栈高度O(logn)，而不管哪种情况栈的每一层处理时间都是O(n)，所以，平均情况（最佳情况也是平均情况）的时间复杂度O(nlogn)，最差情况的时间复杂度为O(n^2)。

扩展资料

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序，它采用了一种分治的策略，通常称其为分治法。快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

（1）首先设定一个分界值，通过该分界值将数组分成左右两部分。

（2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

（3）然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

（4）重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

十大经典排序算法（动图演示） 之 桶排序

9、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

9.1 算法描述

9.2 图片演示

9.3 代码实现

9.4 算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

文章转自

排序算法概述

十大排序算法：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序、希尔排序、计数排序，基数排序，桶排序

稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。

算法的复杂度往往取决于数据的规模大小和数据本身分布性质。

时间复杂度 ： 一个算法执行所耗费的时间。

空间复杂度 ：对一个算法在运行过程中临时占用存储空间大小的量度。

常见复杂度由小到大 ：O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n)

在各种不同算法中，若算法中语句执行次数(占用空间)为一个常数，则复杂度为O(1)；

当一个算法的复杂度与以2为底的n的对数成正比时，可表示为O(log n)；

当一个算法的复杂度与n成线性比例关系时，可表示为O (n)，依次类推。

冒泡、选择、插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为

（一遍找元素O(n)，一遍找位置O(n)）

快速、归并、堆基于分治思想，log以2为底，平均时间复杂度往往和O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）相关

而希尔排序依赖于所取增量序列的性质，但是到目前为止还没有一个最好的增量序列 。例如希尔增量序列时间复杂度为O(n2)，而Hibbard增量序列的希尔排序的时间复杂度为 ， 有人在大量的实验后得出结论;当n在某个特定的范围后希尔排序的最小时间复杂度大约为n^1.3。

从平均时间来看，快速排序是效率最高的：

快速排序中平均时间复杂度O(nlog n)，这个公式中隐含的常数因子很小，比归并排序的O(nlog n)中的要小很多，所以大多数情况下，快速排序总是优于合并排序的。

而堆排序的平均时间复杂度也是O(nlog n)，但是堆排序存在着重建堆的过程，它把根节点移除后，把最后的叶子结点拿上来后需要重建堆，但是，拿上的值是要比它的两个叶子结点要差很多的，一般要比较很多次，才能回到合适的位置。堆排序就会有很多的时间耗在堆调整上。

虽然快速排序的最坏情况为排序规模（n）的平方关系，但是这种最坏情况取决于每次选择的基准， 对于这种情况，已经提出了很多优化的方法，比如三取样划分和Dual-Pivot快排。

同时，当排序规模较小时，划分的平衡性容易被打破，而且频繁的方法调用超过了O(nlog n)为

省出的时间，所以一般排序规模较小时，会改用插入排序或者其他排序算法。

一种简单的排序算法。它反复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。这个工作重复地进行直到没有元素再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为元素会经由交换慢慢“浮”到数列的顶端。

1.从数组头开始，比较相邻的元素。如果第一个比第二个大(小)，就交换它们两个；

2.对每一对相邻元素作同样的工作，从开始第一对到尾部的最后一对，这样在最后的元素应该会是最大(小)的数；

3.重复步骤1~2，重复次数等于数组的长度，直到排序完成。

首先，找到数组中最大（小）的那个元素；

其次，将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换）；

再次，在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最大（小）者。

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

为了给要插入的元素腾出空间，我们需要将插入位置之后的已排序元素在都向后移动一位。

插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组。

一种基于插入排序的快速的排序算法。简单插入排序对于大规模乱序数组很慢，因为元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1 次移动。

希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序，同时该算法是突破O(n^2）的第一批算法之一。

希尔排序是把待排序数组按一定数量的分组，对每组使用直接插入排序算法排序；然后缩小数量继续分组排序，随着数量逐渐减少，每组包含的元素越来越多，当数量减至 1 时，整个数组恰被分成一组，排序便完成了。这个不断缩小的数量，就构成了一个增量序列。

在先前较大的增量下每个子序列的规模都不大,用直接插入排序效率都较高，尽管在随后的增量递减分组中子序列越来越大,由于整个序列的有序性也越来越明显,则排序效率依然较高。

从理论上说，只要一个数组是递减的，并且最后一个值是1，都可以作为增量序列使用。有没有一个步长序列,使得排序过程中所需的比较和移动次数相对较少,并且无论待排序列记录数有多少,算法的时间复杂度都能渐近最佳呢？但是目前从数学上来说，无法证明某个序列是“最好的”。

常用的增量序列

希尔增量序列 ：{N/2, (N / 2)/2, ..., 1}，其中N为原始数组的长度，这是最常用的序列，但却不是最好的

Hibbard序列：{2^k-1, ..., 3,1}

Sedgewick序列：{... , 109 , 41 , 19 , 5，1} 表达式为

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。

为了提升性能，有时我们在半子表的个数小于某个数（比如15）的情况下，对半子表的排序采用其他排序算法，比如插入排序。

若将两个有序表合并成一个有序表，称为2-路归并，与之对应的还有多路归并。

快速排序（Quicksort）是对冒泡排序的一种改进，也是采用分治法的一个典型的应用。

首先任意选取一个数据（比如数组的第一个数）作为关键数据，我们称为基准数(Pivot)，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序，也称为分区（partition）操作。

通过一趟快速排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数组变成有序序列。

为了提升性能，有时我们在分割后独立的两部分的个数小于某个数（比如15）的情况下，会采用其他排序算法，比如插入排序。

基准的选取：最优的情况是基准值刚好取在无序区数值的中位数，这样能够最大效率地让两边排序，同时最大地减少递归划分的次数，但是一般很难做到最优。基准的选取一般有三种方式，选取数组的第一个元素，选取数组的最后一个元素，以及选取第一个、最后一个以及中间的元素的中位数（如4 5 6 7, 第一个4, 最后一个7, 中间的为5, 这三个数的中位数为5, 所以选择5作为基准）。

Dual-Pivot快排：双基准快速排序算法，其实就是用两个基准数, 把整个数组分成三份来进行快速排序，在这种新的算法下面，比经典快排从实验来看节省了10%的时间。

许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或者不一定要一次就将他们排序，很多时候，我们每次只需要操作数据中的最大元素（最小元素），那么有一种基于二叉堆的数据结构可以提供支持。

所谓二叉堆，是一个完全二叉树的结构，同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在一个二叉堆中，根节点总是最大（或者最小）节点。

堆排序算法就是抓住了这一特点，每次都取堆顶的元素，然后将剩余的元素重新调整为最大（最小）堆，依次类推，最终得到排序的序列。

推论1：对于位置为K的结点 左子结点=2 k+1 右子结点=2 (k+1)

验证：C:2 2 2+1=5 2 (2+1)=6

推论2：最后一个非叶节点的位置为 (N/2)-1，N为数组长度。

验证：数组长度为6，(6/2)-1=2

计数排序对一定范围内的整数排序时候的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限于对整数进行排序，而且待排序元素值分布较连续、跨度小的情况。

计数排序是一个排序时不比较元素大小的排序算法。

如果一个数组里所有元素都是整数，而且都在0-K以内。对于数组里每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，利用某种函数的映射关系将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序）。

桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做排序即可。

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。基数排序不是基于比较的算法。

基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。

基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

MSD 从高位开始进行排序

LSD 从低位开始进行排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶

计数排序：每个桶只存储单一键值

桶排序：每个桶存储一定范围的数值

有时，待排序的文件很大，计算机内存不能容纳整个文件，这时候对文件就不能使用内部排序了（我们一般的排序都是在内存中做的，所以称之为内部排序，而外部排序是指待排序的内容不能在内存中一下子完成，它需要做内外存的内容交换），外部排序常采用的排序方法也是归并排序，这种归并方法由两个不同的阶段组成：

采用适当的内部排序方法对输入文件的每个片段进行排序，将排好序的片段（成为归并段）写到外部存储器中（通常由一个可用的磁盘作为临时缓冲区），这样临时缓冲区中的每个归并段的内容是有序的。

利用归并算法，归并第一阶段生成的归并段，直到只剩下一个归并段为止。

例如要对外存中4500个记录进行归并，而内存大小只能容纳750个记录，在第一阶段，我们可以每次读取750个记录进行排序，这样可以分六次读取，进行排序，可以得到六个有序的归并段

每个归并段的大小是750个记录，并将这些归并段全部写到临时缓冲区（由一个可用的磁盘充当）内了，这是第一步的排序结果。

完成第二步该怎么做呢？这时候归并算法就有用处了。