跳到主要内容

任务五 典型算法举例

知识点​

子任务一 排序算法​

1.什么是选择排序法？​

选择排序是最基础的算法。在要排序的一组数中，假设第一个元素是最小值，然后依次与后面的元素作比较，如果有更小的值，就让其交换位置，以此类推重复这样的操作，直到最后完成排序。

选择排序流程图（图1-2）：

开始
↓
输入数组arr的值
↓
i=0
↓
判断 i < arr.length-1
├─ N → 输出arr数组 → 结束
└─ Y → m=i, j=i+1
      ↓
      判断 j < arr.length
      ├─ N → 判断 m≠i
      │       ├─ N → i++ → 返回判断 i < arr.length-1
      │       └─ Y → t=arr[i], arr[i]=arr[m], arr[m]=t → i++ → 返回判断 i < arr.length-1
      └─ Y → 判断 arr[j] < arr[m]
              ├─ Y → m=j → j++ → 返回判断 j < arr.length
              └─ N → j++ → 返回判断 j < arr.length

2.什么是冒泡排序法？​

冒泡排序就是从一组序列中的第一个元素开始，依次对相邻的两个元素进行比较，如果前一个元素大于后一个元素则交换它们的位置。反之，如果前一个元素小于或等于后一个元素，则不交换它们，以此类推，直到比较到最后一个元素为止。

当这样的操作进行完毕，该序列中最大的元素都被置于序列末尾，最小的元素都被置于序列开始，就像水中的气泡冒到了水面一样，所以被称之"冒泡排序法"。

冒泡排序流程图（图1-3）：

开始
↓
输入数组arr的值
↓
i=0
↓
判断 i < arr.length-1
├─ N → 输出arr数组 → 结束
└─ Y → j=0
      ↓
      判断 j < arr.length-i-1
      ├─ N → i++ → 返回判断 i < arr.length-1
      └─ Y → 判断 arr[j] > arr[j+1]
              ├─ Y → t=arr[j], arr[j]=arr[j+1], arr[j+1]=t → j++ → 返回判断 j < arr.length-i-1
              └─ N → j++ → 返回判断 j < arr.length-i-1

3.什么是插入排序法？​

插入排序就是在排序开始前，设想有排序区和未排序区两个区域。并且先将这组序列的第一个元素看作在排序区里，其他元素再未排序区里。排序开始时，每次将未排序区第一个元素取出用于和排序区中元素比较（从后往前），若满足条件（较大或者较小），则将排序区中元素往后移动一个位置。以此类推，直到完成排序。

插入排序流程图（图1-4）：

开始
↓
输入数组arr的值
↓
i=1
↓
判断 i < arr.length
├─ N → 输出arr数组 → 结束
└─ Y → c=arr[i], j=i-1
      ↓
      判断 j≥0 且 arr[j] > c
      ├─ Y → arr[j+1]=arr[j], j=j-1 → 返回判断 j≥0 且 arr[j] > c
      └─ N → arr[j+1]=c, i=i+1 → 返回判断 i < arr.length

子任务二 查找算法​

4.什么是顺序查找法？​

顺序查找也称线性搜索，是在一个已知无序（或有序）队列中找出与给定关键字相同的值的具体位置。原理是让关键字与队列中的第1个（或最后1个）位置的值逐个比较，直到找出与给定关键字相同的值为止。它的缺点是效率低下。

顺序查找流程图（图1-5）：

开始
↓
输入数组arr的值，t=1（t为要查找的数），i=0
↓
判断 i < arr.length
├─ N → 输出未找到 → 结束
└─ Y → 判断 arr[i] == t
        ├─ Y → 输出i → 结束
        └─ N → i=i+1 → 返回判断 i < arr.length

5.什么是二分查找法？​

二分查找是一种高效的搜索算法，适用于有序数组。它通过不断将搜索范围缩小一半来查找目标值，直到找到目标值或确定目标值不存在。

假设我们要在一个有序数组中查找目标值。我们首先将搜索范围设定为整个数组，然后找出数组中间位置的元素。如果该元素等于目标值，则查找成功；如果该元素大于目标值，则目标值可能在数组的前半部分；如果该元素小于目标值，则目标值可能在数组的后半部分。

接下来，我们将搜索范围缩小为前半部分或后半部分，并重复上述过程，直到找到目标值或确定目标值不存在。

二分查找流程图（图1-6）：

开始
↓
输入数组arr的值，t=1（t为要查找的数）
left=0, right=arr.length-1
↓
判断 left < right
├─ N → 输出未找到 → 结束
└─ Y → mid=(left+right)/2
      ↓
      判断 arr[mid] == t
      ├─ Y → 输出mid → 结束
      └─ N → 判断 arr[mid] < t
              ├─ Y → left=mid+1 → 返回判断 left < right
              └─ N → right=mid-1 → 返回判断 left < right

子任务三 递归算法​

6.什么是阶乘法？如何用递归实现？​

阶乘是指从1到给定数字之间所有正整数的乘积，例如4的阶乘式是 4*3*2*1，结果是24。通过观察可以发现，在计算的时候，后面数总是由前面的数减1得到的。因此我们可以用递归算法来实现阶乘。

例如所要求的数是n，则阶乘式是 n × (n-1) × (n-2) × ... × 2 × 1，得到的积是x，x就是n的阶乘。

注意：0的阶乘始终为1。

阶乘法流程图（图1-7）：

开始
↓
输入需要计算的数字n
↓
判断 n ≤ 1
├─ Y → 输出1 → 结束
└─ N → 计算n的阶乘：n × factorial(n-1)
        ↓
        输出 n × factorial(n-1)
        ↓
        结束

7.什么是斐波那契数列？如何用递归实现？​

斐波那契数列，又称黄金分割数列。因数学家莱昂纳多·斐波那契以兔子繁殖为例引入，因此又称"兔子数列"，其数值为：1、1、2、3、5、8、13、21、34……

通过观察可以发现，这个数列从第3项开始，每一项都等于前两项之和。因此在数学上，这一数列以如下递推的方法定义：

  • F(0) = 1
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) （n≥2，n∈N⁺）

斐波那契数列流程图（图1-8）：

开始
↓
输入n
↓
判断 n ≤ 1
├─ Y → n=0则返回0，n=1则返回1 → 结束
└─ N → 调用斐波那契数列过程(n-1) 和 (n-2)
        ↓
        计算和并返回
        ↓
        结束