广告位联系
返回顶部
分享到

通俗易懂的C语言快速排序和归并排序的时间复杂度分析

C语言 来源:互联网 作者:佚名 发布时间:2023-01-28 22:21:49 人浏览
摘要

今天面试的时候,被问到归并排序的时间复杂度,这个大家都知道是O(nlogn),但是面试官又继续问,怎么推导出来的。这我就有点懵了,因为之前确实没有去真正理解这个时间复杂度

今天面试的时候,被问到归并排序的时间复杂度,这个大家都知道是O(nlogn),但是面试官又继续问,怎么推导出来的。这我就有点懵了,因为之前确实没有去真正理解这个时间复杂度是如何得出的,于是就随便答了一波(理解了之后,发现面试的时候答错了......)。

归并排序和快速排序,是算法中,非常重要的两个知识点,同时也是在面试中被问的非常频繁的内容,我明知如此,却没有彻底理解,真是太不应该了。所以,今天这篇博客就来分析一下这两种排序算法的时间复杂度是如何得出的。我查了许多篇博客,很多都是通过公式进行分析,十分难理解,下面我就结合自己的理解,使用通俗易懂的方式进行描述(为了好理解,可能会有些啰嗦)。

归并排序的时间复杂度分析

了解归并排序的应该都知道,归并排序的时间复杂度是O(nlogn),且这个时间复杂度是稳定的,不随需要排序的序列不同而产生波动。那这个时间复杂度是如何得来的呢?我们可以这样分析,假设我们需要对一个包含n个数的序列使用归并排序,并且使用的是递归的实现方式,那么过程如下:

  • 递归的第一层,将n个数划分为2个子区间,每个子区间的数字个数为n/2;
  • 递归的第二层,将n个数划分为4个子区间,每个子区间的数字个数为n/4;
  • 递归的第三层,将n个数划分为8个子区间,每个子区间的数字个数为n/8;

......

  • 递归的第logn层,将n个数划分为n个子区间,每个子区间的数字个数为1;

我们知道,归并排序的过程中,需要对当前区间进行对半划分,直到区间的长度为1。也就是说,每一层的子区间,长度都是上一层的1/2。这也就意味着,当划分到第logn层的时候,子区间的长度就是1了。而归并排序的merge操作,则是从最底层开始(子区间为1的层),对相邻的两个子区间进行合并,过程如下:

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

......

  • 在第二层,每个子区间长度为n/4,总共有4个子区间,每相邻两个子区间进行合并,总共合并2次。n个数字都会被遍历一次,所以这一层的总时间复杂度为O(n);
  • 在第一层,每个子区间长度为n/2,总共有2个子区间,只需要合并一次。n个数字都会被遍历一次,所以这一层的总时间复杂度为O(n);

通过上面的过程我们可以发现,对于每一层来说,在合并所有子区间的过程中,n个元素都会被 操作一次,所以每一层的时间复杂度都是O(n)。而之前我们说过,归并排序划分子区间,将子区间划分为只剩1个元素,需要划分logn次。每一层的时间复杂度为O(n),共有logn层,所以归并排序的时间复杂度就是O(nlogn) 。

上面的描述算是非常详细了,应该不会太难理解。如果上面的过程还是不太理解,那么我们通过另外一种更直观的方式进行分析。上面描述的是递归的过程,下面我们通过非递归(迭代)方式实现的归并排序,再来分析一波,这种方式更加直观(为什么不直接通过非递归的方式描述,而是先通过递归的方式分析,是因为上面的过程也可以用来分析快速排序)。下面是通过非递归方式实现的归并排序代码,其中有两处分析时间复杂度的关键点,我标注出来了(重点关注注释):

**

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

/**

 * 此方法用来定义子区间大小,子区间大小从1->2->4->8 ... ->n/2

 * 可以近似地认为进行了logn次

 */

public static void merge(int[] arr) {

    // 关键点1:划分子区间,每一次的子区间长度是上一次的两倍,所以这个循环需要执行logn次

    for(int i = 1;i<arr.length;i *= 2){

        // 关键点2:此方法每次执行的时间复杂度为O(n),具体看下方

        mergeSort(arr,i);

    }

}

/**

 * 以下方法,每次执行的时间复杂度都是O(n),

 * 因为需要将arr数组的每gap个数子,作为一个子区间,

 * 然后对相邻的两个子区间执行归并排序的merge操作,

 * 所以在这个方法中,arr数组中的每一个数都会在merge操作中,

 * 被处理一次,所以下面这个方法的时间复杂度为O(n)

 */

public static void mergeSort(int[] arr, int gap) {

    int[] tmp = new int[arr.length];

    int index = 0;

    int start1 = 0;

    int end1 = start1 + gap - 1;

    int start2 = end1 + 1;

    int end2 = (start2 + gap - 1)>=arr.length?arr.length-1:start2+gap-1;

    while(start2<arr.length){

        while(start1<=end1&&start2<=end2){

            if(arr[start1]<arr[start2]){

                tmp[index++] = arr[start1++];

            }else{

                tmp[index++] = arr[start2++];

            }

        }

        while(start1<=end1){

            tmp[index++] = arr[start1++];

        }

        while(start2<=end2){

            tmp[index++] = arr[start2++];

        }

        start1 = end2+1;

        end1 = start1 + gap - 1;

        start2 = end1 + 1;

        end2 = (start2 + gap - 1)>=arr.length?arr.length-1:start2+gap-1;

    }

    while(start1<arr.length){

        tmp[index++] = arr[start1++];

    }

    for(int j = 0;j<tmp.length;j++){

        arr[j] = tmp[j];

    }

}

上面的代码,merge方法中的循环需要循环logn次,每次循环都调用一次mergeSort方法,mergeSort方法的时间复杂度为O(n),所以很容易得出归并排序的时间复杂度为O(nlogn)。

快速排序的时间复杂度

了解快速排序的应该知道,快速排序的时间复杂度在O(nlogn)~ O(n^2)之间,下面我就来分别分析这两种情况:

(一)快速排序的最好情况O(nlogn)

这种情况下,其实和上面通过递归分析的归并排序很类似,理解了归并排序的时间复杂度分析,那这里应该也很好理解。快速排序的实现方式,就是在当前区间中选择一个轴,区间中所有比轴小的数都需要放到轴的左边,而比轴大的数则放到轴的右边。在理想的情况下,我们选取的轴刚好就是这个区间的中位数。也就是说,在操作之后,正好将区间分成了数字个数相等的左右两个子区间。此时就和归并排序基本一致了:

  • 递归的第一层,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个数排好序。而每一次操作都需要遍历一次剩下的所有元素,这个操作的时间复杂度是O(n),所以总时间复杂度为O(n^2)。

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

总结

以上内容,就是我基于自己的理解,对快速排序和归并排序时间复杂度的分析。为了更好理解,我的描述都尽可能的详细,所以可能会有点啰嗦,但是我认为还是很通俗易懂的。希望这篇博客能够为之前对这两种排序算法理解不是特别清晰的人提供帮助,同时,若上面的内容存在错误或不足,欢迎指正或补充。


版权声明 : 本文内容来源于互联网或用户自行发布贡献,该文观点仅代表原作者本人。本站仅提供信息存储空间服务和不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权, 违法违规的内容, 请发送邮件至2530232025#qq.cn(#换@)举报,一经查实,本站将立刻删除。
原文链接 : https://www.cnblogs.com/tuyang1129/p/12857821.html
相关文章
  • Matlab实现绘制高阶版本韦恩图(upset图)

    Matlab实现绘制高阶版本韦恩图(upset图)
    韦恩图随着阶数升高会越来越复杂,当阶数达到7或者以上时几乎没办法绘制: 但是使用upset图却可以比较轻易的绘制: 两种类型图的对应关
  • 通俗易懂的C语言快速排序和归并排序的时间复杂
    今天面试的时候,被问到归并排序的时间复杂度,这个大家都知道是O(nlogn),但是面试官又继续问,怎么推导出来的。这我就有点懵了,
  • C语言学习基础知识分享

    C语言学习基础知识分享
    写在前面 我们正式开始接触到C语言,这是我在学习过C语言后重新写的博客,我把之前的稍微优化了一下,希望能用更加朴素的语言和大家分享
  • C语言基础知识分享续篇

    C语言基础知识分享续篇
    写在前面 好了,现在我们开始C语言的第二个部分.今天我们需要看下面几个知识点,都是非常简单的,我们主要认识一下. 数组 我们知道一个一
  • C语言实现求解素数的N种方法

    C语言实现求解素数的N种方法
    哈喽各位友友们,我今天又学到了很多有趣的知识,现在迫不及待的想和大家分享一下!我仅已此文,手把手带领大家探讨利用试除法、筛
  • C语言利用goto语句设计实现一个关机程序

    C语言利用goto语句设计实现一个关机程序
    goto语句其实在平常中我们 除了学习分支语句和循环语句时,介绍循环语句时,才会知道有goto语句这个用法,那读者可能会问:我们还有学
  • VS及Unity安装和使用Nuget包

    VS及Unity安装和使用Nuget包
    一、百科 Nuget是一个包(package)管理平台,确切的说是.net平台的包管理工具,它提供了一系列客户端用于生成,上传和使用包(package),
  • C/C++ Qt实现文章小说人物关系分析

    C/C++ Qt实现文章小说人物关系分析
    一、所需工具软件 1. Visual Stuido 2. C++ 二、使用步骤 1.引入库 代码如下(示例): 1 2 3 4 5 6 7 8 9 10 11 #include QtGuiApplication1.h #includeqDebug #incl
  • C语言实现三子棋的代码

    C语言实现三子棋的代码
    一、问题描述 用 c 语言实现三子棋。 二、基本流程 在写三子棋的代码之前,我们来看看实现这个游戏的逻辑: 1.菜单界面选择开始或者退
  • C++ system()函数的常用用法(全网最新大全)
    一.推荐: 1. system(pause) 这是萌新最常用的函数了,运行后会有个暂停的效果,在制作游戏的时候也很常见 通常用于暂停或等待用户了解完信
  • 本站所有内容来源于互联网或用户自行发布,本站仅提供信息存储空间服务,不拥有版权,不承担法律责任。如有侵犯您的权益,请您联系站长处理!
  • Copyright © 2017-2022 F11.CN All Rights Reserved. F11站长开发者网 版权所有 | 苏ICP备2022031554号-1 | 51LA统计