数组的一些题目

### 数组的一些题目 #### 一、选择排序与插入排序 **知识点：** - **排序算法**：排序算法是计算机科学中的基础算法之一，用于对数据进行升序或降序排列。 - **选择排序**：一种简单直观的比较排序算法。它的工作原理是通过在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 - **插入排序**：一种简单直观的比较排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 - **递归与迭代**：递归是一种算法或过程设计策略，其中函数直接或间接地调用自身；迭代则是一种重复执行同一段代码块直到满足某个条件为止的过程。 **选择排序：** - **递归实现：** ```cpp void recursiveSelectionSort(int array[], int p, int q) { if (p < q) { int min = p; for (int j = p + 1; j <= q; j++) if (array[j] < array[min]) min = j; swap(array[min], array[p]); recursiveSelectionSort(array, p + 1, q); } } ``` 该函数首先检查`p`是否小于`q`，如果是，则找到从`p`到`q`之间的最小元素下标，并与`p`位置的元素交换。之后递归地对剩下的子数组执行相同的操作。 - **迭代实现：** ```cpp void iterativeSelectionSort(int array[], int n) { for (int i = 0; i < n - 1; i++) { int min = i; for (int j = i + 1; j < n; j++) if (array[j] < array[min]) min = j; swap(array[min], array[i]); } } ``` 该函数通过迭代的方式实现了同样的功能。外层循环控制排序轮数，内层循环用于找到未排序部分的最小值。 **插入排序：** - **递归实现：** ```cpp void recursiveInsertionSort(int array[], int p, int q) { if (p < q) { recursiveInsertionSort(array, p, q - 1); int key = array[q + 1]; int j = q; while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } array[j + 1] = key; } } ``` 该函数首先递归地对子数组进行排序，然后将最后一个元素插入到正确的位置上。 - **迭代实现：** ```cpp void iterativeInsertionSort(int array[], int n) { for (int i = 1; i < n; i++) { int j = i - 1; int key = array[i]; while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } array[j + 1] = key; } } ``` 该函数同样通过迭代的方式实现了插入排序的功能。对于每个待插入的元素，通过向后移动比它大的元素来为新元素腾出位置。 #### 二、回文字符串判断 **知识点：** - **回文**：指正读反读都能读通的词语、句子等，如“level”。 - **字符串处理**：包括字符串的遍历、比较、截取等操作。 - **字符判断**：判断字符是否属于指定的字符集，例如判断是否为字母或数字。 **回文字符串判断：** ```cpp bool testPalindrome(char str[], int start, int end) { if (start == end) return true; if (str[start] != str[end]) return false; else return testPalindrome(str, start + 1, end - 1); } bool isLetter(char c) { if (c > 47 && c < 58) return true; // 数字 if (c > 64 && c < 91) return true; // 大写字母 if (c > 96 && c < 123) return true; // 小写字母 return false; } ``` **分析：** - `testPalindrome` 函数用于判断一个字符串是否为回文。该函数递归地比较字符串首尾两端的字符是否相同，直到首尾两端的字符相遇。 - `isLetter` 函数用于判断一个字符是否为字母或数字。这里通过ASCII码值范围来判断字符类型。 - 在主函数中，首先读入一行字符，利用`isLetter`函数过滤掉非字母数字字符，然后调用`testPalindrome`函数进行判断。