关于快速排序和归并排序的时间复杂度分析

目录

一、快排时间复杂度分析

二、归并排序时间复杂度分析

三、写在最后

一、快排时间复杂度分析

快速排序的时间复杂度在O(nlogn)~ O(n^2)之间，下面我分别分析这两种情况：

（一）快速排序的最好情况O（nlogn）

快速排序的实现方式，就是在当前区间中选择一个x，区间中所有比x小的数都需要放到x的左边，而比x大的数则放到右边。在理想的情况下，我们选取的分界点刚好就是这个区间的中位数。也就是说，在操作之后，正好将区间分成了满足数字个数相等的左右两个子区间（快排是按照值的大小划分，个数可能相等，可能不等）。此时就和归并排序基本一致了：

递归的第一层，n个数被划分为2个子区间，每个子区间的数字个数为n/2；

递归的第二层，n个数被划分为4个子区间，每个子区间的数字个数为n/4；

递归的第三层，n个数被划分为8个子区间，每个子区间的数字个数为n/8;

  …

递归的第logn层，n个数被划分为n个子区间，每个子区间的数字个数为1；

以上过程与归并排序基本一致，而区别就是，归并排序是从最后一层开始进行merge操作，自底向上；而快速排序则从第一层开始交换区间中数字的位置，是自顶向下的。但是，merge操作和快速排序的调换位置操作，时间复杂度是一样的，对于每一个区间，处理的时候，都需要遍历一次区间中的每一个元素。这也就意味着，快速排序和归并排序一样，每一层的总时间复杂度都是O（n），因为需要对每一个元素遍历一次。而且在最好的情况下，同样也是有logn层，所以快速排序最好的时间复杂度为O（nlogn）。

（二）快速排序的最坏情况O（n^2）

对于每一个区间，我们在处理的时候，选取的轴刚好就是这个区间的最大值或者最小值。比如我们需要对n个数排序，而每一次进行处理的时候，选取的轴刚好都是区间的最小值。于是第一次操作，在经过调换元素顺序的操作后，最小值被放在了第一个位置，剩余n-1个数占据了2~n个位置；第二次操作，处理剩下的n-1个元素，又将这个子区间的最小值放在了当前区间的第1个位置，以此类推…每次操作，都只能将最小值放到第一个位置，而剩下的元素，则没有任何变化。所以对于n个数来说，需要操作n次即n层，才能为n个数排好序。而每一次操作都需要遍历一次剩下的所有元素，这个操作的时间复杂度是O（n），所以总时间复杂度为O（n^2）。

其实上面的过程，我们可以换一个角度理解：每次操作，找出最小值放到剩余区间的第一个位置，这不就是选择排序的实现方式吗？而选择排序的时间复杂度就是O(n ^ 2)，所以上面的过程也就O（n^2）。

二、归并排序时间复杂度分析

归并排序的时间复杂度是O（nlogn），且这个时间复杂度是稳定的，不随需要排序的序列不同而产生波动。下面我来分析一下~

假设我们需要对一个包含n个数的序列使用归并排序，并且使用的是递归的实现方式，那么过程如下：

递归的第一层，将n个数划分为2个子区间，每个子区间的数字个数为n/2；

递归的第二层，将n个数划分为4个子区间，每个子区间的数字个数为n/4；

递归的第三层，将n个数划分为8个子区间，每个子区间的数字个数为n/8;

  …

递归的第logn层，将n个数划分为n个子区间，每个子区间的数字个数为1；

  在整个归并排序的过程中，每一层的子区间，长度都是上一层的1/2。分析可知，当子区间的长度为1时，共划分了logn层。而归并排序的merge操作，则是从最底层开始（子区间为1的层），对相邻的两个子区间进行合并，过程如下：

在第logn层（最底层），每个子区间的长度为1，共n个子区间，每相邻两个子区间进行合并，总共合并n/2次。n个数字都会被遍历一次，所有这一层的总时间复杂度为O（n）；

  …

在第2层，每个子区间长度为n/4，总共有4个子区间，每相邻两个子区间进行合并，总共合并2次。n个数字都会被遍历一次，所以这一层的总时间复杂度为O（n）；

在第1层，每个子区间长度为n/2，总共有2个子区间，只需要合并一次。n个数字都会被遍历一次，所以这一层的总时间复杂度为O（n）；

  通过上面的过程我们可以发现，对于每一层来说，在合并所有子区间的过程中，n个元素都会被操作一次，所以每一层的时间复杂度都是O（n），共有logn层，所以归并排序的时间复杂度就是O（nlogn）。

————————————————

版权声明：本文为CSDN博主「qing小星星」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：