00:00
各位同学,我们现在继续来讲解数据结构和算法的下一个内容叫排序算法,那么同学们都知道排序算法呢有很多,而且从目前来看呢,就是在。我们去找工作的时候,面试和笔试呢,尤其是笔试经常出现排序算法。所以说排序算法对于我们来说呢,是一个非常重要的知识点,而且有些排序算法呢,还不是很好理解,所以说同学们听这个章节的时候要认真听,首先我们先来对排序算法做一个基本的介绍。那么同学们可以看到排序,它也叫排序算法,就说有些人简称。叫排序,其实排序呢,准确的讲它是一种算法。也就是说排序其实呃,不能说是一种数据结构了,它其实是利用我们的一个数组,然后根据什么呢?根据指定的一个顺序排列的一个过程,因此它其实是一个算法。
01:08
所以说我们说排序其实就是排序算法,它就是一种算法,那么排序它的这么一个分类有哪些呢?我们来做一个简单的介绍,排序它有两大类,第一大类呢,叫做内部排序,听这个名字就知道什么意思了,就说我们需将需要处理的所有数据加载到内部存储器,内部存储器就是说的再通俗一点就是内存。在这个内存中完成排序就一次搞定,就是把所有数据先加到内存里面去,然后呢,通过一个算法就说先把我们的数据放到内存中。对,在一个内存中就完成排序就完事了,这是一种,那么还有一种呢,就是叫做外部排序法。那么外部排序法呢?什么时候会用?就是当我们数据量很大。
02:01
数据量很大,比如说我们这个数据量有10亿个数据。11个数据我要对它排序,但是呢,我们的内存。不足以加载这么大的一个数据量。这时我们需要借助外部存储来进行排序,也就是说,我们可能是先加载一部分。排序完了过后呢,再加载另外一部分排序,然后再合并。这个就称之为外部排序法,那么同学们看常见的排序算法呢,如左图啊,如右图啊,这边这个图是右图,这写错了,如右图。把它改下,如右图。那么我们常见的排序有哪些呢?同学们看到我们重点讲的是内部排序,也就是说同学们在面试和笔试的时候呢,重点考察你的内部排序,内部排序分成这么几大类,插入、选择、交换、规定和基数,基数排序呢也是叫统治法。同学们应该有些有些同学听过统排序,其实技术排序就是统排序的一个扩展。
03:05
也就说你学会基数排序了,统排序也就没有任没有任何问题。那么插入排序里面分成两大类,又又分两个两个类,一个叫直接插入,一个叫希尔排序,就share排序。还有一个选择排序里面呢,有简单排序,有堆排序,堆排序是属于选择排序的一种。交换排序呢?有冒泡,这个是大家最熟悉的了,还有一种叫快速排序,它也属于一种交换式的。规避排序技术排序呢后面会讲,那么对于我们一般的程序员的程序员来讲呢,我们常见的排序法有这三种,一个是直接插入。简单选择,还有一个冒泡,这三种呢是很多。这个培训机构还有学校里面要求同学们掌握的。但是随着。这个时代的发展呢,目前对我们程序员的要求,尤其是排序算法呢,要求越来越高了,因此我们在这一套课程里面呢,我们会把这八种排序法全部给大家讲解,也就是说直接插入希尔简单排序堆,排序冒泡快速规定和技术我们都给大家讲了。
04:16
希望同要求同学们把这八种排序法都把它掌握了,OK。好,这是我们对排序算法的一个分类的说明,那么我们接着再来看下一个幻灯片。就是算法的一个。时间复杂度的一个说法。那么我们刚才讲过,排序算法有这么多,那么怎么去衡量?怎么去衡量一个程序,或者说或者这样说嘛,去衡量一个算法。执行的时间呢,就他执行的时间谁长谁短呢,目前来说有两种方式可以来做,第一种呢比较简单,就是事后统计法,所谓事后统计法就是说咱这样子考虑。
05:03
就说我们这写了一段程序。我们直接把它运行起来。运行。然后运行过后呢,就来看看这个花了多少时间就完了,这样子我们就可以看到这段程序它执行的时间是多长。如果我要比较两个程序,是不是我把另外一段程序也运行,再看时间。这个就叫事后统计,就是先运行了过后再看一下它花费花费的时间是多长,但是这种事后统计法呢,有问有几个问题,有两个问题,第一个呢,我们如果要通过这个事后统计法,我们需要先运行这个程序。对吧,周老师那个运行程序,那就运行一下呗,但是有这样问题,假如我们这个程序它非常的耗费时间。比如这个算法在统计个海量数据的时候,它要耗费多长时间呢?比如他要十分钟。那你去运行十分钟,你还在这等呢,对不对,这个很麻烦的。
06:03
第二个更麻烦的是,我们也知道一个程序它运行的时间的长短呢,除了跟你这个程序算法本身相关,还跟我们的硬件也有关系,比如说我们这个计算机的内存很大,我们这个计算机的CPU很强,它用了它能它能够支持多线程那。这个就。不能够完全体会体现出你这个程序。本身的优越性的,比如说我有一个A程序。这个A程序呢,我是在这个,呃,一号一号计算机运行的。那么我这有个B程序,这个B程序呢,是在二号。计算机运行的。那你敢保证?如果A程序运行的时间短,就一定说A程序比B程序算法好吗?不一定,因为你这个还有计算机硬件的不同了,对不对?所以说我们说这个事后统计存在两个问题,第一个就是首先要实际运行。
07:07
这个呢,就可能会花费我们很长时间。第二个。第二个就是说它以依赖于硬件。还跟你操作系统有关系呢。所以说我们这个事后统计呢,如果你一定要用的话,这需要有一个前提什么呢?如果我们用这种事后统计法来统计,要求在同一台计算机的相同状态下运行,才能比较哪个算法速度更快。所以说如果你你这样做呢,还可以简单的测试一下,但是这个呢,毕竟是思路统计。所以说我们提出还有第二一种来衡量算法的实验,就是事前估算方。事前估算法呢,就是通过分析某个算法的时间复杂度,来判断哪个算法更优秀。就是我们通过这个时间复杂度来看你的这个代码。
08:01
你你的代码这个时间复杂度谁。更。更优秀对吧,所以说我们这个算法时间复杂度呢,就从这引出来了,它可以通过得到一段程序的时间复杂度来判断哪个算法更优秀,所以说一会呢,我们就要开始讲解算法的时间复杂度,那这样子我们把刚才讲的内容呢,做一个简单的。一个半书,好,我们刚才讲的是排序算法的一个基本介绍,来捋一捋刚才讲的内容。一会呢,我们再往里面深入,好吧,我们插入一个分页符,这个叫排序算法。OK,叫排序算法。没问题吧,诶这个地方摁错了排序算法。那排序算法呢,首先。诶,往这儿来一下啊,排序算法呢,首先我们给大家说了一下排序算法的基本介绍。
09:04
排序算法的基本介绍,我们先给同学们说了一下排序算法是什么?对不对,我们说排序算法是什么。同学们看,排序算法呢,它其实是将一组数据。将一组数据按照指定的顺序。进行排列的过程,这个其实就是排序,那么指定的顺序怎么排成一个有序的呢?这个就用到算法,所以这个算法呢,它的英文叫sort。Algori algoriism这个这个单词就是算法的意思明白,所以说我们说排序算法其实简称排序,但是排序再说一遍啊,排序不是数据结构,它是一种算法。别别把它搞蒙圈了啊,第二个呢,我们给大家讲一下排序算法的这么一个分类的问题,我们把它捋一捋。说排序算法呢,分成这么几类,一个呢叫做内部排序,内部排序就是它所有的数据在内部存储器,也简称内存。
10:05
就是把数据加在内存里面去进行排序,还有一个呢,我们叫做外部排序法,那外部排序法什么时候会用到呢?就是数据量很大。比如说我刚才举的十个亿数据加不进去怎么办呢?需要外部存储,比如说用到文件磁盘这些类型,比如说你会用到外部的这个,比如说你会用到文件磁盘对吧,文件等。就简单写到这儿。可以放到文件里面去好,那么常见的这个常见的排序有哪些呢?我们这有一张图,把它拿过来给同学们放,这这个大家要做到心里有数啊,比如说面试官问你说请问。同学,同学,请问你咱们常见的内部排序有哪些?你不能只答一个插入选择和冒泡,这个档次就太low了,你得把这八种都说出来。就是说直接插入希尔简单排序,堆排序,冒泡快速规定和技术,技术排序呢,也是我们这个统排序的一个升级版或叫扩展版,理解好,当我们把这个讲完以后呢,我们就给同学们说了一下算法时间复杂度,那么算算法时间度复杂度呢,我先做了一个基本的介绍,就说。
11:17
什么时候咱们会用到时间复杂度呢?就是去度量或者要衡量都可以啊,衡量一个程序或者算法,它执行的时间谁谁短谁更谁更,这个短就谁谁更。时间有两种,一种叫事后统计,叫事前估算。事后统计呢有两个问题,一个是必须执行,第二个他跟你的硬件有关系,因此你要用事后统计,还得要求在同一个计算机同一个状态。这个这个限制就是,呃,就比较大了,事前估算呢,我们就可以通过计算它的时间复杂度来判断哪个算法更优,所以说这个地方我们就抛出了,或者或者引出了我们后面马上要讲的时间复杂度的这个问题。
12:05
好,刚才我们讲的一个就是事后统计。二是各种计法。对吧,15亿吧,还有呢,就是刚才我们说的事前事前估算。但事先估算呢,就是用到时间复杂度。那么时间复杂度到底怎么算?怎么推算一个时间复杂度?我们常见的时间复杂度又有哪几类呢?我们放到下一个视频为大家讲解。好这个视频,我们先为大家讲解到这里。
我来说两句