跳到主要内容

十：排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍

前言​

  • 前面的数据结构到了现在可以到一段落了。
  • 从第十章开始就要学习 排序算法了。
  • 排序算法主要学习(按学习顺序来排列、也是难易程度)：冒泡排序、简单选择排序、直接插入排序、希尔排序、快速排序、归并排序、基数排序、堆排序等等。
  • 这一节主要是介绍排序的分类、还有衡量算法的优劣的方法时间复杂度，还有常用的时间复杂度等等。

一、排序算法介绍​

排序也称 排序算法 (Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。

1.1 排序分类​

1、 内部排序:；
指将需要处理的所有数据都加载到内部存储器中进行排序。 2、 外部排序法：；
数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。 3、 常见的排序算法分类(见下图):；
 

二、算法的时间复杂度​

2.1 度量一个程序(算法)执行时间的两种方法​

1、 事后统计的方法；
这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。 2、 事前估算的方法；
通过分析某个算法的 时间复杂度 来判断哪个算法更优.

2.2 时间频度​

2.2.1 基本介绍​

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

2.2.2 举例说明-基本案例​

比如计算1-100所有数字之和, 我们设计两种算法：
第一种就是 100，第二种就是 1。