排序也称排序算法(排序算法),排序是将<强>一组数据,<强>依指定的顺序强进行<强>排列的过程。
1),<强>内部排序:指将需要处理的所有数据都加载到<强>内部存储器(内存)中进行排序。
2) <>强外部排序法:数据量过大,无法全部加载到内存中,需要借助<强>外部存储(文件等)强进行排序。
常见的排序算法分类
算法的时间复杂度度量一个程序(算法)执行时间的两种方法
1,事后统计的方法这种方法可行,但是有两个问题:一是要想对设计的算法的运行性能进行评测,需要实际运行该程序;
二是所得时间的统计量依赖于计算机的硬件,软件等环境因素,这种方式,要在同一台计算机的相同状态下运行,才能比较那个算法速度更快。
2,事前估算的方法通过分析某个算法的时间复杂度来判断哪个算法更优。
时间频度:一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T (n)。
<强>举例说明,基本案例
比如计算1 - 100所有数字之和,我们设计两种算法:
1,一般情况下,算法中的基本操作语句的重复执行次数是问题规模n的某个函数,用T (n)表示,若有某个辅助函数f (n),使得当n趋近于无穷大时,T (n)/f (n)的极限值为不等于零的常数,则称f (n)是T (n)的同数量级函数。记作T (n)=O (f (n)),称O (f (n)),为算法的渐进时间复杂度,简称时间复杂度。
2, T (n)不同,但时间复杂度可能相同。如:T (n)=n² n + 7 + 6与T (n)=3 n² + 2 n + 2它们的T (n)不同,但时间复杂度相同,都为O (n²)。
3,计算时间复杂度的方法:
用常数1代替运行时间中的所有加法常数,T (n)=n² n + 7 + 6=比;T (n)=n² + 7 n + 1修改后的运行次数函数中,只保留最高阶项,T (n)=n² + 7 n + 1=比;T (n)=n²去除最高阶项的系数T (n)=n²=比;T (n)=n²=比;O (n²)常见的时间复杂度
<强>说明:
常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(日志2 n) <Ο(n) <Ο(nlog 2 n) <Ο(n 2) <Ο(n 3) <Ο(n k) <Ο(2 n),随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低
从图中可见,我们应该尽可能避免使用指数阶的算法
无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O (1)
上述代码在执行的时候,它消耗的时候并不随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用O(1)来表示它的时间复杂度。
2)对数阶O (log 2 n)
说明:在循环里面,每次都将我乘以2,乘完之后,我距离n就越来越近了。假设循环x次之后,我就大于2了,此时这个循环就退出了,也就是说2的x次方等于n,那么x=日志2 n也就是说当循环日志2 n次以后,这个代码就结束了。因此这个代码的时间复杂度为:O (log 2 n),2。O (log n)的这2个时间上是根据代码变化的,我* 3=,则是
