排序算法

一：排序算法介绍

排序：排序是将一组数据，依指定的顺序进行排列的过程

排序分类：

1. 内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。

2. 外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

3. 常见的排序算法分类：

   

二：算法的时间复杂度

1. 度量一个程序执行时间的两种方法

1. 时候统计的方法

   这种方法可行，但是有两个问题：一是想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件下、软件等环境因素，这种方式，要在同一台计算机的相同状态下运行，才能 比较哪个算法速度更快。

2. 事前估算的方法

   通过分析某一个算法的时间复杂度来判断哪个算法更优。

2. 算法的时间复杂度：

1.时间频度：

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

​ 举例说明：

特点：

• 常数项可以忽略
• 低次项可以忽略
• 系数可以忽略

2.时间复杂度：

3.常见的时间复杂度：

1. 常数阶O1

常数阶O1

2.对数阶O(log2n)

3.线性阶O(n)

4.线性对数阶O(nlogN)

5.平方阶O(n*n)

6.立方阶O(nxnxn),K次方阶O(nxxxx…xxxxk)

4.平均时间复杂度和最坏时间复杂度

三：算法的空间复杂度