常见排序算法及其时间复杂度

一、内部排序：

  在一个排序工作的执行过程中,如果待排序的记录全部保存在内存,这种工作就称为内排序；针对外存(磁盘、磁带等)数据的排序工作称为外排序。内排序中的归并排序算法是大多数外排序算法的基础。
在考虑算法时,最基本的问题是其时间和空间复杂度。为了在某种合理的抽象层次上考虑它们的时间复杂度和空间复杂度，需要确定关注的基本操作，以其作为时间单位，时间复杂性反映排序过程中这个(或这些)操作的执行次数。还需确定某种抽象的空间单位。
现在要做的是数据记录排序,而且基于关键码比较,比较之后有可能要调整数据记录的位置(顺序)。根据这些情况可以确定两种最重要的基本操作：

• 比较关键码的操作,通过这种操作确定数据的顺序关系。
• 移动数据记录的操作,用于调整记录的位置和/或顺序。

  在下面讨论各种算法时,总是以被排序序列的长度(即序列中元素的个数)作为问题规模参数n,讨论在完成整个排序的过程中执行上述两种操作的次数(的量级)。以此作为评价算法效率的度量(时间复杂度)。
理论研究已经得到了一个明确的结论:基于关键码比较的排序问题，时间复杂度是o(nlogn)

o(nlogn)。也就是说,实现这一过程的任何算法都不可能优于o(nlogn)o(nlogn)。人们已经开发出来的一些算法达到了这样的效率,因此已经是最优的算法。
在分析排序算法的空间复杂度时，应该考虑的是为了执行这个算法所需要的空间，因为这部分空间需求由具体算法决定，反映了排序算法的特征。应该看到，这种算法的目的是对已有的序列排序，算法完成后被排序的序列依然存在。因此，算法执行中使用的空间是临时性的辅助空间，用过之后就可以释放了。
如果某个排序算法能保证:对于待排序的序列里任一对排序码相同的记录RiRi​和RjRj​；在排序之后的序列里RiRi​与Rj

Rj​的前后顺序不变，就称这种排序算法是稳定的。也就是说，稳定的算法能够维持序列中所有排序码相同记录的相对位置。如果一个排序算法不能保证上述条件，它就是不稳定的。
适应性： 如果一个排序算法对接近有序的序列工作得更快,就称这种算法具有适应性。具有适应性的算法也有实际价值，因为实际中常常需要处理接近排序的序列。

1.稳定的排序算法

1.1 冒泡排序

1.1.1 冒泡排序流程

https://blog.csdn.net/u012864854/article/details/79404463

1. 比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。
3. 针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。
4. 持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。
   
   时间复杂度：

• 其外层循环执行 N−1

N−1次。内层循环最多的时候执行NN次，最少的时候执行1次，平均执行(N+1)/2(N+1)/2 次。所以循环体内的比较交换约执行 (N−1)(N+1)/2=(N2−1)/2(N−1)(N+1)/2=(N2−1)/2（按照计算复杂度的原则，去掉常数，去掉最高项系数，其复杂度为O(N2)

• O(N2)。
• 对于一个已经有序的数组，算法完成第一次外层循环后就会返回。实际上只发生了 N−1
• N−1次比较，所以最好的情况下，该算法复杂度是O(N)
  • O(N)。
    空间复杂度：
  • 最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；
  • 最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
  • 平均的空间复杂度为：O(1)；

  1.1.2 冒泡排序的实现

  https://blog.csdn.net/weixin_41725746/article/details/90300689
  使用双重for循环，内层变量为i， 外层为j，在内层循环中不断的比较相邻的两个值（i, i+1）的大小，如果i+1的值大于i的值，交换两者位置，每循环一次，外层的j增加1，等到j等于n-1的时候，结束循环。

  1.2 插入排序

  1.2.1 插入排序流程

  https://blog.csdn.net/llzk_/article/details/51628574
  插入排序是将一组数据分成有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少，直到待插入组元素个数为0。在插入过程中涉及到了元素的移动。为了排序方便，一般将数据第一个元素视为有序组，其他均为待插入组。
  
  时间复杂度：

  • 插入排序的时间复杂度分析。在最坏情况下，数组完全逆序，插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，……，插入第N个元素，要考虑前 N−1
  N−1 个元素。因此，最坏情况下的比较次数是 1+2+3+...+(N−1)1+2+3+...+(N−1)，等差数列求和，结果为 N2/2N2/2，所以最坏情况下的复杂度为 O(N2)
• O(N2)。
• 最好情况下，数组已经是有序的，每插入一个元素，只需要考查前一个元素，因此最好情况下，插入排序的时间复杂度为O(N)

• O(N)。
  空间复杂度：
• 算法的空间复杂度很清楚:计算中只用了两个简单变量,用于辅助定位和完成序列元素的位置转移。因此算法的空间复杂度是O(1),与序列大小无关

1.2.2 插入排序的实现

  排序以从小到大排序为例，元素0为第一个元素，插入排序是从元素1开始，尽可能插到前面。插入时分插入位置和试探位置，元素i的初始插入位置为i，试探位置为i-1，在插入元素i时，依次与i-1,i-2······元素比较，如果被试探位置的元素比插入元素大，那么被试探元素后移一位，元素i插入位置前移1位，直到被试探元素小于插入元素或者插入元素位于第一位。

1.3 归并排序

1.3.1 归并排序流程

https://www.cnblogs.com/chengxiao/p/6194356.html
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，实现步骤如下：


时间复杂度：
归并的时间复杂度分析：主要是考虑两个函数的时间花销：
一、数组划分函数mergeSort()；
二、有序数组归并函数_mergeSort()；
_mergeSort()函数的时间复杂度为O(n)，因为代码中有2个长度为n的循环（非嵌套），所以时间复杂度则为O(n)；
简单的分析下元素长度为n的归并排序所消耗的时间 T[n]：调用mergeSort()函数划分两部分，那每一小部分排序好所花时间则为 T[n/2]，而最后把这两部分有序的数组合并成一个有序的数组_mergeSort()函数所花的时间为 O(n)；
公式：T[n]=2T[n/2]+O(n)

T[n]=2T[n/2]+O(n)；
所以得出的结果为：T[n]=O(nlogn)T[n]=O(nlogn)
因为不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O(nlogn)

O(nlogn)

空间复杂度：
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n+logn

n+logn；所以空间复杂度为: O(n)。

以时间换空间：
归并排序虽然比较稳定，在时间上也是非常有效的（最差时间复杂度和最优时间复杂度都为 O(nlogn) )，但是这种算法很消耗空间，一般来说在内部排序不会用这种方法，而是用快速排序；外部排序才会考虑到使用这种方法。

1.4 桶排序

1.4.1 桶排序流程

https://www.cnblogs.com/skywang12345/p/3602737.html
桶排序(Bucket Sort)的原理是将数组分到有限数量的桶子里。
假设待排序的数组a中共有N个整数，并且已知数组a中数据的范围[0, MAX)。在桶排序时，创建容量为MAX的桶数组r，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个"桶"。
在排序时，逐个遍历数组a，将数组a的值，作为"桶数组r"的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组a[3]=5，则将r[5]的值+1。

再将数据放到桶中之后，再通过一定的算法，将桶中的数据提出出来并转换成有序数组。就得到我们想要的结果了。

时间复杂度：
假设原始数列的元素个数是N，桶的数量的M，平均每个桶内的元素数量的N/M

• 求最值，计算量N
• 初始化桶，计算量M
• 数列的元素放入桶，计算量N
• 每个桶内元素排序，由于使用了O(n log n)算法，计算量是M(N/M * log N/M)=N(log N/M)
• 最后返回排好序的集合，计算量是N

  综上所述，计算量是 3N+M+ N(log N - log M)，去掉系数O(N+M+N(log N - log M))
假如M=N，则时间复杂度O(N+M)，近似O(N)

空间复杂度：
很明显是原始数组的空间N 加上 桶的空间M，是N+M。

1.4.2 桶排序的实现

https://www.cnblogs.com/sfencs-hcy/p/10612422.html

1.5 基数排序

1.5.1 基数排序流程

https://www.cnblogs.com/skywang12345/p/3603669.html
基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：

在上图中，首先将所有待比较数值统一为统一位数长度，接着从最低位开始，依次进行排序。

1. 按照个位数进行排序。
2. 按照十位数进行排序。
3. 按照百位数进行排序。

排序后，数列就变成了一个有序序列。

时间复杂度：
该算法所花的时间基本是在把元素分配到桶里和把元素从桶里串起来；把元素分配到桶里：循环 length 次；
把元素从桶里串起来：这个计算有点麻烦，看似两个循环，其实第二循环是根据桶里面的元素而定的，可以表示为：k×buckerCount；其中 k 表示某个桶中的元素个数，buckerCount 则表示存放元素的桶个数；

有几种特殊情况：
第一、所有的元素都存放在一个桶内：k = length，buckerCount = 1；
第二、所有的元素平均分配到每个桶中：k = length/ bukerCount，buckerCount = 10；（这里已经固定了10个桶）。所以平均情况下收集部分所花的时间为：length （也就是元素长度 n）

综上所述：
时间复杂度为：posCount * (length + length) ；其中 posCount 为数组中最大元素的最高位数；简化下得：O( k*n ) ；其中k为常数，n为元素个数；

空间复杂度：
该算法的空间复杂度就是在分配元素时，使用的桶空间；所以空间复杂度为：O（10 × length）= O （length）

1.5.2 基数排序的实现

https://blog.csdn.net/will130/article/details/45196575

1.6 二叉树排序

1.6.1 二叉树排序流程

https://blog.csdn.net/qq_40803710/article/details/80945367
二叉树排序的基本原理：先构建一颗空树，使用第一个元素作为根节点，如果之后的元素比第一个小，则放到左子树，否则放到右子树，之后按中序遍历。
二叉搜索树的性质：
（1）每个结点都有一个作为搜索依据的关键码（key）也就是数据域，所有节点的关键码互不一样。
（2）左子树（如果存在）上的所有结点的关键码都小于根结点的关键码。
（3）右子树（如果存在）上的所有结点的关键码都大于根结点的关键码。
（4）左右子树也是二叉搜索树。

2. 不稳定的排序算法

2.1 选择排序

2.1.1 选择排序流程

简单选择排序：
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

• 第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
• 第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
• 以此类推…
• 第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，直到整个序列按关键码有序。

  不难看出，寻找最小的元素需要一个循环的过程，而排序又是需要一个循环的过程。因此显而易见，这个算法的时间复杂度是O(n*n)的。这就意味值在n比较小的情况下，算法可以保证一定的速度，当n足够大时，算法的效率会降低。并且随着n的增大，算法的时间增长很快。因此使用时需要特别注意。

时间复杂度：
选择排序的复杂度分析。第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。共比较的次数是 (N - 1) + (N - 2) + … + 1，求等差数列和，得(N−1+1)∗N/2=N2/2

(N−1+1)∗N/2=N2/2。舍去最高项系数，其时间复杂度为 O(N^2)。
虽然选择排序和冒泡排序的时间复杂度一样，但实际上，选择排序进行的交换操作很少，最多会发生 N - 1次交换。
而冒泡排序最坏的情况下要发生N^2 /2交换操作。从这个意义上讲，交换排序的性能略优于冒泡排序。而且，交换排序比冒泡排序的思想更加直观。

空间复杂度：
最优的情况下（已经有顺序）复杂度为：O(0) ；最差的情况下（全部元素都要重新排序）复杂度为：O(n )；平均的时间复杂度：O(1)

2.2 希尔排序

2.2.1 希尔排序流程

https://www.cnblogs.com/chengxiao/p/6104371.html
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

时间复杂度：
希尔排序的复杂度和增量序列是相关的：

• {1,2,4,8,…}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n^2)
• Hibbard提出了另一个增量序列{1,3,7，...,2k−1}，这种序列的时间复杂度(最坏情形)为O(n1.5)
• Sedgewick提出了几种增量序列，其最坏情形运行时间为O(n1.3),其中最好的一个序列是{1,5,19,41,109,…}

2.3 堆排序

2.3.1 堆排序流程

https://blog.csdn.net/yuzhihui_no1/article/details/44258297
整个排序主要核心就是堆化过程，堆化过程一般是用父节点和他的子节点进行比较，取最大的孩子节点和其进行交换；但是要注意这应该是个逆序的，先排序好子树的顺序，然后再一步步往上，到排序根节点上。然后又相反（因为根节点也可能是很小的）的，从根节点往子树上排序。最后才能把所有元素排序好；具体的操作可以看代码，也可以看看下面的图示：

时间复杂度：
假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；

  那么总的时间计算为：s=2(i−1)∗(k−i)

s=2(i−1)∗(k−i)；其中 i 表示第几层，2(i−1)

2(i−1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；

  S=2(k−2)∗1+2(k−3)∗2.....+2∗(k−2)+2(0)∗(k−1)

S=2(k−2)∗1+2(k−3)∗2.....+2∗(k−2)+2(0)∗(k−1) ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；

  等式左右乘上2，然后和原来的等式相减，就变成了：
S=2(k−1)+2(k−2)+2(k−3).....+2−(k−1)

S=2(k−1)+2(k−2)+2(k−3).....+2−(k−1)

  除最后一项外，就是一个等比数列了，直接用求和公式：S=a1[1−(qn)]/(1−q)

S=a1​[1−(qn)]/(1−q)；

  S=2k−k−1

S=2k−k−1；又因为k为完全二叉树的深度，所以 (2k)<=n<(2k−1)

(2k)<=n<(2k−1)，总之可以认为：k = logn （实际计算得到应该是 log(n+1) < k <= logn ）;

  综上所述得到：S = n - longn -1，所以时间复杂度为：O(n)

更改堆元素后重建堆时间：O(nlogn)

推算过程：
1、循环 n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：logn(n-1) = nlogn - logn ；

   综上所述：堆排序的时间复杂度为：O(nlogn)

空间复杂度：
因为堆排序是就地排序，空间复杂度为常数：O(1)

2.4 快速排序

2.4.1 快速排序流程

快速排序的基本思想是：

1. 先从数列中取出一个数作为基准数；
2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；
3. 再对左右区间重复第二步，直到各区间只有一个数。
   
   最优情况下时间复杂度：
   快速排序最优的情况就是每一次取到的元素都刚好平分整个数组(很显然我上面的不是)；
   此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；
   下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：
   T[n]=2T[n/2]+n

T[n]=2T[n/2]+n ----------------第一次递归
令：n=n/2n=n/2,  =2{2T[n/4]+(n/2)}+n=2{2T[n/4]+(n/2)}+n -------------第二次递归
=22T[n/(22)]+2n=22T[n/(22)]+2n
令：n=n/(22)n=n/(22), =222T[n/(23)]+n/(22)+2n=222T[n/(23)]+n/(22)+2n -------第三次递归
=23T[n/(23)]+3n=23T[n/(23)]+3n
……………………………………
令：n=n/(2(m−1))n=n/(2(m−1)), =2mT[1]+mn

1. =2mT[1]+mn ---------第m次递归(m次后结束)

 当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。
得到：T[n/(2m)]=T[1]

T[n/(2m)]=T[1] ===>> n=2mn=2m ====>> m=lognm=logn；
T[n]=2mT[1]+mnT[n]=2mT[1]+mn ；其中m=lognm=logn;
T[n]=2(logn)T[1]+nlogn=nT[1]+nlogn=n+nlognT[n]=2(logn)T[1]+nlogn=nT[1]+nlogn=n+nlogn ；其中n为元素个数
又因为当n >= 2时：nlogn>=nnlogn>=n (也就是logn > 1)，所以取后面的 nlognnlogn；
综上所述：快速排序最优的情况下时间复杂度为：O(nlogn)

O(nlogn)

最差情况下时间复杂度
最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;
综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )

平均时间复杂度
快速排序的平均时间复杂度也是：O(nlogn)

空间复杂度：
就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；

• 最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况；
• 最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况。

二、外部排序：

https://www.cnblogs.com/codeMedita/p/7425291.html
有时，待排序的文件很大，计算机内存不能容纳整个文件，这时候对文件就不能使用内部排序了（这里做一下说明，其实所有的排序都是在内存中做的，这里说的内部排序是指待排序的内容在内存中就可以完成，而外部排序是指待排序的内容不能在内存中一下子完成，它需要做内外存的内容交换），外部排序常采用的排序方法也是归并排序，这种归并方法由两个不同的阶段组成：

1. 采用适当的内部排序方法对输入文件的每个片段进行排序，将排好序的片段（成为归并段）写到外部存储器中（通常由一个可用的磁盘作为临时缓冲区），这样临时缓冲区中的每个归并段的内容是有序的。
2. 利用归并算法，归并第一阶段生成的归并段，直到只剩下一个归并段为止。
   例如要对外存中4500个记录进行归并，而内存大小只能容纳750个记录，在第一阶段，我们可以每次读取750个记录进行排序，这样可以分六次读取，进行排序，可以得到六个有序的归并段，如下图：
   

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

  完成第二步该怎么做呢？这时候归并算法就有用处了，算法描述如下：

1. 将内存空间划分为三份，每份大小250个记录，其中两个用作输入缓冲区，另外一个用作输出缓冲区。首先对Segment_1和Segment_2进行归并，先从每个归并段中读取250个记录到输入缓冲区，对其归并，归并结果放到输出缓冲区，当输出缓冲区满后，将其写道临时缓冲区内，如果某个输入缓冲区空了，则从相应的归并段中再读取250个记录进行继续归并，反复以上步骤，直至Segment_1和Segment_2全都排好序，形成一个大小为1500的记录，然后对Segment_3和Segment_4、Segment_5和Segment_6进行同样的操作。
2. 对归并好的大小为1500的记录进行如同步骤1一样的操作，进行继续排序，直至最后形成大小为4500的归并段，至此，排序结束。

可以用一个图示表示上述算法的归并效果：

以上对外部排序如何使用归并算法进行排序进行了简要总结，提高外部排序需要考虑以下问题：

1. 如何减少排序所需的归并趟数。
2. 如果高效利用程序缓冲区，使得输入、输出和CPU运行尽可能地重叠。
3. 如何生成初始归并段（Segment）和如何对归并段进行归并。