[TOC]

计算机科学导论学习笔记

第 4 部分 计算机软件与算法

此部分包含第7、8、9、10章，包含了计算机操作系统、问题求解算法、程序设计语言之旅、软件工程等相关知识，加深我们对开发的认识，为后续开发打下一个基础。

原文地址: https://mp.weixin.qq.com/s/4anuwyRs95GMHHNvtMIz8w

第 8 章.数据算法

数据算法（分步解决问题的过程）是学习计算机编程开发的核心，只有在了解数据算法的前提下才能，做出更好、更高效的软件，在今后的学习中我会针对《数据结构与算法》进行详细学习，此节先简单的作为一个入门了解。

8.1 算法概念

(1) 非标准定义

算法是一种逐步解决问题或完成任务的方法，按照这种定义算法完全独立于计算机系统。

例如，算法在接收一组输入数据，同时产生一组输出数据。

例如，使用求最大值算法来求得输入五个数中的最大值。

输入：算法需输入一组5个整数（12 、8、 13、 9、 11）。

过程：使用在算法中定义的 Largest 变量，依次对比输入的整数，将比对的最大值赋予给它。

输出：算法执行完毕输出 Largest 值（13）。

细化

为了算法能在所有程序中应用则需要对其进行细化，实际上示例算法细分为两步。

• 步骤01.将Lagest遍历初始化为负无穷。
• 步骤02.如果第1数值大于Lagest，则将其赋予给Lagest变量。

• 步骤03.如果第2数值大于Lagest，则将其赋予给Lagest变量。

• 步骤04.如果第3数值大于Lagest，则将其赋予给Lagest变量。

• 步骤05.如果第4数值大于Lagest，则将其赋予给Lagest变量。

• 步骤06.如果第5数值大于Lagest，则将其赋予给Lagest变量。

泛化

为了算法不仅仅在简单的几个数之间最大值而是从 n 个正数中找到最大值，为了提高效率以及减少编写步骤，我们可以在计算机循环此步骤n次，然后再将求得的最大值输出。

(2) 更正式定义

算法：它是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。

定义良好：算法必须是一组定义良好且有序的指令集合。

明确步骤：算法的每一步都必须有清晰、明白的定义，不能出现一个操作符有多重意思。

产生结果：算法必须产生结果，否则该算法就没有意义。

在有限时间内终止: 算法必有有终止条件，不能无限循环下去。

8.2 算法结构

结构化程序或算法定义了顺序、判断（选择）和循环三种基础结构，仅仅使用这三种结构就可以使程序或算法容易理解、调试或修改。

• 顺序结构：最简单的指令结构， 算法（最终是程序）都是指令序列，顾名思义按顺序执行。

• 判断(选择)结构: 条件指令结构，当算法程序指令中需要检测一个条件满足时或者不满足时从而分别执行不同的操作。

• 循环(重复)结构：当有相同指令需要重复执行时，使用循环(重复)结构来解决。

---

8.3 算法表示

当下，常常使用图示、UML以及伪代码等几种表示算法。

(1) UML

统一建模语言（UML）: 是算法的图形表示法，它使用“大图”的形式掩盖了算法的所有细节，它只显示算法从开始到结束的整个流程。

例如，使用UML来表示算法的三种基本结构。

weiyigeek.top-UML表示三种基本结构

温馨提示：UML具有许多灵活性，如果在假的部分没有操作，那么判断结构就能简化

(2) 伪代码

伪代码（pseudo code）：是算法的一种类似英语的表示法，当下并没有伪代码的标准，有些人使用得过细，有些人则使用得过粗。有些人用一种很像英语的代码，有些人则用和Pascal编程语言相似的语法。

我认为只要能简要介绍问题解决的实现即可，至于采用那种由自己水平而定。

weiyigeek.top-伪代码表示三种结构

例如，使用伪代码来表示算法的三种基本结构。

---

8.4 基本算法

(1) 求和乘积

计算机科学中常用的算计就是求和与乘积。

• 求和：实现两个或者多个数值相加。
• 乘积：实现讲个或者多个数值相乘。

此处以Javascript语言为例进行演示：

# 定义
var a = 2;
var b = 6;
# 相加步骤
a + b
# 结果 
8

例如，求x^n次方值

# 定义：
var x = 2;
var n = 3;
var result = 1;

# 阶乘步骤
while ( n > 0 ) {
 result *= x 
 n--;
}
result

# 结果
8

(2) 求最值

即通常求得一组数据中的最大值（最小值）算法，即判断两个整数的最大值或者最小值。

此处以JavaScript语言为例进行演示：

# 定义
var x = 2;
var y = 3;

# 最值与最小值步骤
function max (x,y) {
 return x > y ? x:y
}
function min (x,y) {
 return x < y ? x:y
}

# 结果
max(x,y)
3
min (x,y)
2

(3) 排序算法

计算机科学中最普遍的应用是排序，它根据数据的值对其按顺序排列。其中最常用、最简单、效率最低的三种排序算法选择排序、冒泡排序、插入排序，他们也是当今计算机科学中使用快速排序的基础。

当然除了上述简单的算法外，还有更高级、高效的排序算法，例如快速排序、堆排序、Shell排序、桶排序、合并排序、基排序等，但此章节不做详细讲解，在后续深入学习数据结构与算法时在详细说明。

当前程序中为了决定哪种算法更适合特定的程序，需要一种叫做算法复杂度的度量，例如冒泡排序的复杂度为O(n)。

平方阶 (O(n2)) 排序各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 : 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数: 希尔排序;

线性阶 (O(n)) 排序：基数排序，此外还有桶、箱排序。

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

image-20220926151604850

名词解释：

• n：数据规模.
• k：”桶”的个数.
• In-place：占用常数内存，不占用额外内存.
• Out-place：占用额外内存.
• 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同.

---

1.冒泡排序(Bubble Sort)：其也是使用两重循环，外层循环每迭代一次，内层循环每次迭代则将某一原数置于顶部（头部）。

• 算法步骤:

  比较相邻的元素。如果第一个比第二个大，就交换他们两个。

  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

  针对所有的元素重复以上的步骤，除了最后一个。

  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

• 时间复杂度：O(n)

• 算法稳定性: 是一种稳定排序算法。

• 排序选择：当n值较大时，冒泡排序比选择排序快。

weiyigeek.top-冒泡p排序示例

• 代码示例：此处以Go语言进行简单演示。

//* 冒泡排序 */
//* 1. 从当前元素起，向后依次比较每一对相邻元素，若逆序则交换 */
//* 2. 对所有元素均重复以上步骤，直至最后一个元素 */
package main
import "fmt"
func bubblesort() {
    var temp int
  arr := [...]int{21, 9, -18, 196, 88, 68, 1}
  length := len(arr)
  fmt.Printf("原始数组: %v \n",arr)
  for i := 0 ; i < length - 1; i++ {
      // 每次循环将最大值放在最右边, if 条件中 > 则为升序，< 则为降序
    for j := 0; j < length - 1 - i; j++ {
        // 注意其与选择排序的不同之处，冒泡是直接相邻下标值两两对比、交换
      if (arr[j] > arr[j+1]) {
        temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp 
      }
    }
    fmt.Printf("第 %d 次循环: %v\n",i+1,arr)
  }
  fmt.Printf("冒泡排序: %v",arr)
}

func main(){
  bubblesort()
}

执行结果：

原始数组: [21 9 -18 196 88 68 1] 
第 1 次循环: [9 -18 21 88 68 1 196]
第 2 次循环: [-18 9 21 68 1 88 196]
第 3 次循环: [-18 9 21 1 68 88 196]
第 4 次循环: [-18 9 1 21 68 88 196]
第 5 次循环: [-18 1 9 21 68 88 196]
第 6 次循环: [-18 1 9 21 68 88 196]
冒泡排序: [-18 1 9 21 68 88 196]

2.选择排序(Selection sort)：该算法使用两重循环，外层循环每扫描时迭代一次，内层循环则在未排列列表中求得最小元素。

• 算法步骤:

  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

  重复第二步，直到所有元素均排序完毕。

• 时间复杂度：O(n^2）
• 稳定性：是一个不稳定的排序算法。
• 排序选择：当n值较小时，选择排序比冒泡排序快。

weiyigeek.top-选择排序示例图

• 代码示例：此处以Go语言进行简单演示。

//* 选择排序 */
//* 1. 从当前元素起，记录当前初始循环索引（i），当当前索引值依次与索引值+1进行对比，如后者比前者小，则记录其索引下标，并将其值赋予给初始循环索引*/
//* 2. 对于下次循环则为 外部初始循环索引i++ ，且内部循环索引为初始循环索引 （i）+1，然后再求最小值。
//* 3. 对所有元素均重复以上步骤，直至最后一个元素 */
package main
import "fmt"
func selectionsort() {
  arr := [...]int{21, 9, -18, 196 , 88, 68, 1}
  length := len(arr)
  fmt.Printf("原始数组: %v \n",arr)
  for i := 0 ; i < length - 1; i++ {
        // 每次循环时将最小值放在最左边，如 if 条件是 > 则为升序，< 则为降序。
        // 最小数的索引为i
        minIndex := i
    for j := i + 1; j < length; j++ {
      if (arr[minIndex] > arr[j]) {
        minIndex = j
      }
    }
        // 注意其与冒泡排序的不同之处，选择是直接下标交换。
        temp := arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = temp 
        
        fmt.Printf("第 %d 次循环: %v\n",i+1,arr)
  }
  fmt.Printf("选择排序: %v",arr)
}

func main(){
  selectionsort()
}

执行结果：

原始数组: [21 9 -18 196 88 68 1] 
第 1 次循环: [-18 9 21 196 88 68 1]
第 2 次循环: [-18 1 21 196 88 68 9]
第 3 次循环: [-18 1 9 196 88 68 21]
第 4 次循环: [-18 1 9 21 88 68 196]
第 5 次循环: [-18 1 9 21 68 88 196]
第 6 次循环: [-18 1 9 21 68 88 196]
选择排序: [-18 1 9 21 68 88 196]

3.插入排序（Insertion Sort）: 其设计类似于Selection Sort与Bubble Sort排序，其工作方式相似玩扑克牌从大到小插入，外层循环每轮都迭代( 0< n <length)，内层循环(外i, 外i > 0,外i--)寻找插入位置。

• 操作步骤：

  将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

  （如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

• 时间复杂度：最好 O(n)，最坏 O (n^2)。

• 空间复杂度：常数阶O(1)。

• 稳定性：是一种稳定排序算法。

weiyigeek.top-插入排序示例

• 排序选择：当n值大于1000的场景下不建议使用插入排序。

//* 插入排序 */
//* 1. 从当前元素起，外层循环下标为0，内层循环下标为 外层循环下标（i）,*/
//* 2. 比较下标[j-1]是否大于下标[j],是则交换其值。
//* 3. 对所有元素均重复以上步骤，直至最后一个元素 */
package main
import "fmt"
func insertionsort() {
  arr := [...]int{21, 9, -18, 196 , 88, 68, 1}
  length := len(arr)
  fmt.Printf("原始数组: %v \n",arr)
  for i := 0 ; i < length; i++ {
        // 先假设每次循环时，将 j 次循环的值按从小到大依次排列，如 if 条件是 > 则为升序，< 则为降序。
    for j := i; j > 0; j-- {
      if (arr[j-1] > arr[j]) {
          temp := arr[j]
              arr[j] = arr[j-1]
              arr[j-1] = temp 
      }
    }
        fmt.Printf("第 %d 次循环: %v\n",i+1,arr)
  }
  fmt.Printf("插入排序: %v",arr)
}

func main(){
  insertionsort()
}

执行结果：

原始数组: [21 9 -18 196 88 68 1] 
第 1 次循环: [21 9 -18 196 88 68 1]
第 2 次循环: [9 21 -18 196 88 68 1]
第 3 次循环: [-18 9 21 196 88 68 1]
第 4 次循环: [-18 9 21 196 88 68 1]
第 5 次循环: [-18 9 21 88 196 68 1]
第 6 次循环: [-18 9 21 68 88 196 1]
第 7 次循环: [-18 1 9 21 68 88 196]
插入排序: [-18 1 9 21 68 88 196]

---

(4) 查找算法

在计算机科学里还有一种常用的算法叫做查找，是一种在列表中确定目标所在位置的算法，两种最基本的查找方法为顺序查找和折半查找.

1.顺序查找(Sequential search)：用于查找无序列表，通常用于查找较小的列表或者不常用的列表。

• 查询步骤：

  顺序査找是从列表起始处开始查找，当找到目标元素或确信查找目标不在列表中时，查找过程结束。

• 图示：

weiyigeek.top-顺序查找

• 代码演示：此处使用Go语言进行演示。

package main
import "fmt"

func sequentialsearch(n int,  numbers []int) int {
  fmt.Printf("原始数组: %v \n", numbers)
  for i, v := range numbers {
    if ( n == v ) {
      return i
    }
  }
  return -1
}

func main(){
  searchNumber := 196
  arr := [...]int{21, 9, -18, 196 , 88, 68, 1}
  index := sequentialsearch(searchNumber, arr[:])
  fmt.Printf("元素 %d 在 arrNumber [ %v ] 中的下标为 %v",searchNumber,arr,index)
}

执行结果：

原始数组: [21 9 -18 196 88 68 1] 
元素 196 在 arrNumber [ [21 9 -18 196 88 68 1] ] 中的下标为 3

2.折半查找: 通常称为二分法, 用于找寻有序列表中的元素，其效率更高，如果元素是无序的则不能使用该方法。

• 查询步骤：

  折半査找是从一个列表的中间元素来测试的，这将能够判别出目标在列表的前半部分还是后半部分。

  如果在前半部分，就不需要査找后半部分。

  如果在后半部分，就不需要查找前半部分。

• 图示：

weiyigeek.top-折半查找示例

• 代码演示：

  package main
  import "fmt"
  func halfsearch(number int, numbers []int) int {
    // 初始化 数组、长度、中值变量
    var i,arr_len,mid int
      
    // 在arr[i...arr_len]之中查找target
    i = 0
    arr_len = len(numbers)
  
      // go 语言没有While关键字所有使用for作为替代，以及使用 break 跳出循环。
    for {
      // 取数组长度中值(灵魂)
      mid = i + (arr_len - i) / 2
      // 刚好等于则直接返回mid，如果大于number则将其中值减一后赋予arr_len，否则将中值赋予 i + 1。
      if numbers[mid] == number {
        return mid
      } else if  numbers[mid] > number  {
        arr_len = mid - 1
      } else {
        i = mid + 1
      }
      
          // 不满足则退出循序，即
      if i > arr_len {
         break
      }
    }
    return -1
  }
  
  func main() {
    searchNumber := 88
    arr := [...]int{-18,1,9,21,68,88,196}
    index := halfsearch(searchNumber, arr[:])
      fmt.Printf("[折半查询]\n元素 %d 在 arrNumber  %v  中的下标为 %v",searchNumber,arr,index)
  }

  执行结果：

  [折半查询]
  元素 88 在 arrNumber  [-18 1 9 21 68 88 196]  中的下标为 5

(5) 迭代递归算法

通常为了解决更复杂的问题，我们会使用迭代或使用递归算法。

迭代: 其算法的定义不涉及算法本身，则算法的迭代的。例如 阶乘的计算（迭代）。

递归: 即算法自我调用的过程。例如 斐波那契数列。

WeiyiGeek

实际上递归计算花费的时间更长且更加困难，那为何我没还要使用递归呢？

递归对于编程人员和程序阅读者在概念上更容易理解。

分别使用迭代与递归算法进行计算阶乘示例：此处以Go语言为例。

package main
import "fmt"
// 使用迭代方式计算阶乘
func factotial_iteration(n int) int {
  result,i := 1,1
  for {
    if (i > n){
      break
    }
    result *= i
    i++
  }
  return result
}

// 使用递归方式计算阶乘
func factotial_recursion(n int) int {
  if ( n == 0) {
    return 1
  } else {
    return n * factotial_recursion(n-1)
  }
}

func main() {
  number := 6
  result := factotial_iteration(number)
  fmt.Printf("使用迭代计算 %d! 阶乘的结果为 %d \n", number, result)

  result = factotial_recursion(number)
  fmt.Printf("使用递归计算 %d! 阶乘的结果为 %d", number, result)
}

执行结果：

使用迭代计算 6! 阶乘的结果为 720 
使用递归计算 6! 阶乘的结果为 720

(6) 子算法

定义

结构化编程的原则要求将算法分成几个单元，称为子算法, 而每个子算法依次又分为更小的子算法，你可将其看做即函数模块。

在每次迭代中，算法SelectionSort调用子算法FindSmallest。

weiyigeek.top-子算法概念示例

使用子算法至少有两个优点，即程序更容易理解，子算法可在主算法中不同地方调用。

结构图

描述：程序员使用的另一个编程工具就是结构图，它是一个高级设计工具，它显示了算法和子算法之间的关系。

结构图是面向过程软件设计阶段的主要工具。

• 模块符号：每个矩形代表编写一个模块，矩形的名字就是其代表的模块的名字。
• 结构图的选择条件：例如表示 条件和异或。
• 结构图中的循环条件：例如表示普通循环和条件循环。
• 结构图的阅读顺序：从上到下，从左到右阅读。

weiyigeek.top-结构图

结构图主要规则：

• 结构图每个矩形都代表一个模块。
• 矩形中的名字就是模块代码的模块名。
• 结构图中只包含模块流程，没有任何代码。
• 公有模块的矩形一般都在右下角画一条双向影线或一块阴影。
• 数据流和标志是可选的，但如果使用则必须命名。
• 输入流和标志是显示垂直线的左端，输出流和标志显示在其右端。