ch4 筛法与查找

1. 函数初探

函数是一个具有特定功能的、相对独立的模块，能够被多次使用。

函数设计的要素：

• 功能：函数的定义

  C++

  /* 
   * bool:    函数的返回值类型
   * isPrime: 函数的名字
   * int n:   函数的参数为 n，类型为 int
   */
  bool isPrime(int n)
  {
      bool bPrime = true;
      for (int i = 2; i * i <= n; i++) {
          if (n % i == 0) {
              bPrime = false;
              break;
          }
      }
      return bPrime;      // 返回一个 bool 类型的值
  }
  

• 模块：函数的声明

  C++

  bool isPrime(int);
  

  有一个函数，名字叫 isPrime，有一个 int 的输入，输出为 bool 类型。函数的声明必须出现在函数调用之前，一般写在 main 函数前面。

• 使用：函数的调用

  C++

  isPrime(n);
  

  调用名字为 isPrime 的函数，判断 \(n\) 是否为素数。

  

  函数的参数：

  • 形式参数：在定义函数时放在函数名称之后的括号中的参数，属于局部变量，其作用域限定在它所在的函数体内。
  • 实际参数：一个具有确定值的表达式，在函数调用时将实际参数赋给形参变量。

2. 数组

• 数组的定义

  C++

  int number[10];
  

  定义了一个大小为 \(10\)，名称为 number，存储 int 型数据的数组，相当于定义了 \(10\) 个 int 类型的变量。

  中括号里面的数必须是整数，并且建议使用常量。视频中说的必须使用常量，是因为 C++ 标准的不同，较新的标准（比如 C++11）均支持使用变量来定义数组大小，称为变长数组，但是我个人还是建议使用常量。

• 数组的初始化

  C++

  int number[10] = {0, 21, 2, 13, 4, 7, 9, 7, 8, 15};
  
  // 下面的写法是正确的，编译器会自动计算并补全数组大小
  int number[] = {0, 21, 2, 13, 4, 7, 9, 7, 8, 15};
  
  // 下面的写法是错误的，因为在定义数组时要让编译器知道变量占多少空间
  int number[];
  

• 数组的赋值

  数组中的每一项都可以作为独立的变量使用、赋值。

  C++

  number[0] = 5;
  cin >> number[1];
  cout << number[x];
  
  // 下面的写法是错误的，因为除了初始化之外，不能对数组进行直接批量赋值
  number = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  
  // 下面的写法是正确的，可以利用循环进行批量赋值
  for (int x = 0; x < 10; x++)
      number[x] = x;
  

3. 埃氏筛

C++

const int N = 100;                          // const 表示定义符号常量
bool seive[N + 1];

for (int i = 2; i <= N; i++)                // 初始化 “筛子” 系统
    seive[i] = true;

for (int d = 2; d * d <= N; d++) {          // 枚举 2 到 N 的平方根之间的每个数 d
    if (seive[d]) {                         // 如果 d 没有被筛掉
        for (int x = d * d; x <= N; x += d) // 用 d 筛掉 100 以内除了 d 之外 d 的倍数
            seive[x] = false;
    }
}

for (int i = 2; i <= N; i++)                // 输出所有没有被筛掉的数
    if (seive[i])
        cout << i << " ";

4. 线性查找

• 扑克牌查找

  C++

  // 初始化 13 张牌
  int cards[13] = {101, 113, 303, 206, 405, 208, 311,
                   304, 410, 309, 112, 207, 402};
  
  int pos = -1;                   // 假设没有黑桃 Q
  for (int i = 0; i < 13; i++) {  // 依次枚举每一张牌
      if (cards[i] == 112) {      // 如果是黑桃 Q
          pos = i;                // 记下位置
          break;                  // 停止枚举
      }
  }
  
  if (pos != -1)
      cout << "黑桃 Q 是第 " << pos + 1 << "张" << endl;
  else
      cout << "没找到" << endl;
  

• 最小值查找

  C++

  int min = 100, pos = -1;            // 初始化当前最小值及位置
  
  for (int i = 0; i < 13; i++) {      // 依次枚举每一张牌
      if (cards[i] % 100 > 7 &&       // 如果比 7 大，并且比最小值还小
          cards[i] % 100 < min) {
          min = cards[i] % 100;       // 更新最小值
          pos = i;                    // 更新位置
      }
  }
  

不管是找特定的值，还是找满足特定条件的元素，基本思想还是一个一个依次枚举，比较的次数和总元素的个数呈线性关系，我们称这种查找方法为线性查找，也称顺序查找。

5. 折半查找

在待查序列有序的情况下，可以采用折半查找，也称二分查找。

C++

int id = -1, low = 0, high = 12;    // 初始化查找范围，假设没有黑桃 Q

while (low <= high) {               // 如果范围内有牌，则一直做
    int mid = (low + high) / 2;     // 选取中间一张
    if (cards[mid] == 112) {        // 如果中间的牌是黑桃 Q
        id = mid;                   // 记下位置
        break;                      // 停止查找
    }
    else if (cards[mid] > 112)      // 否则，如果中间的牌比黑桃 Q 大
        high = mid - 1;             // 更新范围，在左侧寻找
    else
        low = mid + 1;              // 更新范围，在右侧寻找
}

6. 排序问题

• 插入排序

  以下插入排序的思路为简化之后的思路，代码更加简介，推荐使用。

  C++

  void InsertionSort(int cards[], int n)
  {
      for (int i = 1; i < n; i++) {           // 枚举每张待插入的牌
          int tmp = cards[i];                 // 记录待插入的牌
          for (int j = i-1; j >= 0; j--) {    // 枚举从空位置到第一个位置的每一个位置
              if (cards[j] > tmp) {           // 如果当前位置的元素比待插入的牌大
                  cards[j+1] = cards[j];      // 把当前位置的牌向后挪
              }
              else {
                  cards[j+1] = tmp;           // 把待插入的牌插入到当前位置的后继位置
                  break;                      // 结束当前插入过程
              }
          }
      }
  }
  

• 选择排序

  C++

  void SelectionSort(int cards[], int n)
  {
      // 最后一个元素没必要再选择了，因为后面没元素了
      // 换句话讲，单个元素默认有序，这与插入排序中的第一个元素不参与枚举是一致的
      for (int i = 0; i < n - 1; i++) {           // 枚举每个位置 i
          int min = cards[i], min_id = i;         // 假设第 i 个元素最小
          for (int j = i + 1; j < n; j++) {       // 枚举位置 i 之后的每个元素 j
              if (cards[j] < min) {               // 如果比最小值小
                  min = cards[j];                 
                  min_id = j;                     // 标记最小值为元素 j
              }
          }
          cards[mid_id] = cards[i];               // 将最小的牌交换到位置 i 处
          cards[i] = min;
      }
  }