下面是一个简要的 C++ 基础搜索与排序的讲义，包括常见的搜索和排序算法实现及其讲解。

C++ 基础搜索与排序

1. 搜索算法

搜索算法用于在数据结构中查找特定元素。最常见的搜索算法有 线性搜索 和 二分搜索。

1.1 线性搜索 (Linear Search)

线性搜索是一种简单的搜索算法，它从数据结构的第一个元素开始，逐个检查元素，直到找到目标元素为止。如果元素存在，返回其位置，否则返回 -1。

如 STL模板中的 find 函数 std::find 的定义 std::find 是 C++ 标准库中 <algorithm> 头文件中的一个函数，用于在容器中查找指定值。其定义如下：

  1. template< class InputIterator, class T >
  2. InputIterator find( InputIterator first, InputIterator last, const T& value );
  • first 和 last 是容器的迭代器范围。
  • value 是要查找的目标值。
  • 函数返回指向找到的第一个目标值的迭代器。如果没有找到，则返回 last。

算法实现步骤：

  1. 从数组的第一个元素开始，逐个比较。
  2. 如果当前元素与目标元素相等，则返回当前索引。
  3. 如果遍历完数组仍未找到目标元素，则返回 -1。

代码实现：

  1. #include <iostream>
  2. using namespace std;
  4. int linearSearch(int arr[], int size, int target) {
  5.     for (int i = 0; i < size; ++i) {
  6.         if (arr[i] == target) {
  7.             return i;  // 找到目标，返回索引
  8.         }
  9.     }
  10.     return -1;  // 如果未找到目标元素，返回 -1
  11. }
  13. int main() {
  14.     int arr[] = {5, 3, 8, 6, 7, 2};
  15.     int size = sizeof(arr) / sizeof(arr[0]);
  16.     int target = 6;
  18.     int result = linearSearch(arr, size, target);
  19.     if (result != -1) {
  20.         cout << "元素 " << target << " 在索引 " << result << " 处找到" << endl;
  21.     } else {
  22.         cout << "元素 " << target << " 未找到" << endl;
  23.     }
  25.     return 0;
  26. }

时间复杂度：

  • 最坏情况：O(n)，遍历整个数组。
  • 平均情况：O(n)，需要在大部分情况下遍历一半数组。

1.2 二分搜索 (Binary Search)

二分搜索是一种高效的搜索算法，只能在已排序的数组中使用。它通过不断将搜索范围对半分，迅速缩小搜索区间，从而提高查找效率。

算法步骤：

  1. 先将数组排序（如果未排序）。
  2. 确定中间元素，若该元素等于目标元素，则返回其索引。
  3. 如果目标小于中间元素，则在左半部分继续搜索；否则在右半部分继续搜索。
  4. 直到找到目标元素，或者搜索区间为空。

代码实现：

  1. #include <iostream>
  2. using namespace std;
  4. int binarySearch(int arr[], int size, int target) {
  5.     int left = 0, right = size - 1;
  7.     while (left <= right) {
  8.         int mid = left + (right - left) / 2;  // 防止溢出
  10.         if (arr[mid] == target) {
  11.             return mid;  // 找到目标，返回索引
  12.         }
  13.         if (arr[mid] < target) {
  14.             left = mid + 1;  // 在右半部分继续搜索
  15.         } else {
  16.             right = mid - 1;  // 在左半部分继续搜索
  17.         }
  18.     }
  19.     return -1;  // 如果未找到目标元素，返回 -1
  20. }
  22. int main() {
  23.     int arr[] = {2, 3, 5, 6, 7, 8};
  24.     int size = sizeof(arr) / sizeof(arr[0]);
  25.     int target = 6;
  27.     int result = binarySearch(arr, size, target);
  28.     if (result != -1) {
  29.         cout << "元素 " << target << " 在索引 " << result << " 处找到" << endl;
  30.     } else {
  31.         cout << "元素 " << target << " 未找到" << endl;
  32.     }
  34.     return 0;
  35. }

时间复杂度：

  • 最坏情况：O(log n)
  • 平均情况：O(log n)

注意：二分搜索需要数组是已排序的。

2. 排序算法

排序算法用于将数据按一定的顺序排列。常见的排序算法有 冒泡排序、选择排序、插入排序 和 快速排序。

2.1 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法。它通过重复地遍历待排序的数列，比较相邻的元素，如果它们的顺序错误就交换它们，直到整个数列有序。

算法步骤：

  1. 从头到尾遍历数组，比较相邻的元素。
  2. 如果元素顺序错误，就交换它们的位置。
  3. 每一轮遍历后，最大元素将“冒泡”到数组的末尾。
  4. 重复上述过程，直到没有需要交换的元素。

代码实现：

  1. #include <iostream>
  2. using namespace std;
  4. void bubbleSort(int arr[], int size) {
  5.     for (int i = 0; i < size - 1; ++i) {
  6.         for (int j = 0; j < size - 1 - i; ++j) {
  7.             if (arr[j] > arr[j + 1]) {
  8.                 swap(arr[j], arr[j + 1]);  // 交换相邻元素
  9.             }
  10.         }
  11.     }
  12. }
  14. int main() {
  15.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
  16.     int size = sizeof(arr) / sizeof(arr[0]);
  18.     bubbleSort(arr, size);
  20.     cout << "排序后的数组：";
  21.     for (int i = 0; i < size; ++i) {
  22.         cout << arr[i] << " ";
  23.     }
  24.     cout << endl;
  26.     return 0;
  27. }

时间复杂度：

  • 最坏情况：O(n²)
  • 平均情况：O(n²)
  • 最好情况：O(n)，当数组已经排好序时。

2.2 选择排序 (Selection Sort)

选择排序是一种简单的排序算法。它每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。

算法步骤：

  1. 在未排序的部分中找到最小元素。
  2. 将其与未排序部分的第一个元素交换位置。
  3. 重复该过程，直到整个数组有序。

代码实现：

  1. #include <iostream>
  2. using namespace std;
  4. void selectionSort(int arr[], int size) {
  5.     for (int i = 0; i < size - 1; ++i) {
  6.         int minIndex = i;
  7.         for (int j = i + 1; j < size; ++j) {
  8.             if (arr[j] < arr[minIndex]) {
  9.                 minIndex = j;  // 找到最小元素的索引
  10.             }
  11.         }
  12.         swap(arr[i], arr[minIndex]);  // 交换最小元素与当前元素
  13.     }
  14. }
  16. int main() {
  17.     int arr[] = {64, 25, 12, 22, 11};
  18.     int size = sizeof(arr) / sizeof(arr[0]);
  20.     selectionSort(arr, size);
  22.     cout << "排序后的数组：";
  23.     for (int i = 0; i < size; ++i) {
  24.         cout << arr[i] << " ";
  25.     }
  26.     cout << endl;
  28.     return 0;
  29. }

时间复杂度：

  • 最坏情况：O(n²)
  • 平均情况：O(n²)
  • 最好情况：O(n²)

2.3 插入排序 (Insertion Sort)

插入排序通过逐步将未排序部分的元素插入已排序部分，使得每一步得到的都是一个已排序的子数组。

算法步骤：

  1. 从第二个元素开始，逐个插入到前面已经排好序的部分。
  2. 每次插入元素时，将其与已排序部分的元素进行比较，找到正确位置。

代码实现：

  1. #include <iostream>
  2. using namespace std;
  4. void insertionSort(int arr[], int size) {
  5.     for (int i = 1; i < size; ++i) {
  6.         int key = arr[i];
  7.         int j = i - 1;
  9.         // 将大于 key 的元素往右移一位
  10.         while (j >= 0 && arr[j] > key) {
  11.             arr[j + 1] = arr[j];
  12.             j--;
  13.         }
  14.         arr[j + 1] = key;  // 插入 key 到正确位置
  15.     }
  16. }
  18. int main() {
  19.     int arr[] = {12, 11, 13, 5, 6};
  20.     int size = sizeof(arr) / sizeof(arr[0]);
  22.     insertionSort(arr, size);
  24.     cout << "排序后的数组：";
  25.     for (int i = 0; i < size; ++i) {
  26.         cout << arr[i] << " ";
  27.     }
  28.     cout << endl;
  30.     return 0;
  31. }

时间复杂度：

  • 最坏情况：O(n²)，当数组是逆序排列时，每次插入都会导致最大移动。
  • 平均情况：O(n²)，大部分情况下也需要进行大量的比较和移动。
  • 最好情况：O(n)，当数组已经是有序的情况下，插入排序的效率非常高，因为无需进行元素交换。

2.4 快速排序 (Quick Sort)

快速排序是一种分治排序算法，它通过一个基准元素（pivot）将数组分成两部分，将小于基准的元素放在基准的左边，大于基准的元素放在右边，然后分别递归地对这两部分进行排序。

算法步骤：

  1. 选择一个基准元素（通常是数组的第一个、最后一个或随机一个元素）。
  2. 将数组分成两个部分，左边部分的元素小于基准，右边部分的元素大于基准。
  3. 对左、右部分分别递归进行快速排序。
  4. 递归直到数组大小为1或空。

代码实现：

  1. #include <iostream>
  2. using namespace std;
  4. int partition(int arr[], int low, int high) {
  5.     int pivot = arr[high];  // 选择数组的最后一个元素作为基准
  6.     int i = low - 1;  // i 是小于 pivot 的元素的最后一个位置
  8.     for (int j = low; j < high; ++j) {
  9.         if (arr[j] <= pivot) {
  10.             i++;
  11.             swap(arr[i], arr[j]);  // 将小于 pivot 的元素交换到左边
  12.         }
  13.     }
  14.     swap(arr[i + 1], arr[high]);  // 将 pivot 放到正确的位置
  15.     return i + 1;  // 返回基准元素的位置
  16. }
  18. void quickSort(int arr[], int low, int high) {
  19.     if (low < high) {
  20.         int pi = partition(arr, low, high);  // 获取分区点
  22.         quickSort(arr, low, pi - 1);  // 排序左半部分
  23.         quickSort(arr, pi + 1, high);  // 排序右半部分
  24.     }
  25. }
  27. int main() {
  28.     int arr[] = {10, 7, 8, 9, 1, 5};
  29.     int size = sizeof(arr) / sizeof(arr[0]);
  31.     quickSort(arr, 0, size - 1);
  33.     cout << "排序后的数组：";
  34.     for (int i = 0; i < size; ++i) {
  35.         cout << arr[i] << " ";
  36.     }
  37.     cout << endl;
  39.     return 0;
  40. }

时间复杂度：

  • 最坏情况：O(n²)，当每次选取的基准元素是最大或最小元素时（例如在已经有序的数组中，基准总是极端值）。
  • 平均情况：O(n log n)，快速排序大多数情况下能将数组平均分为两部分，形成对数级的递归深度。
  • 最好情况：O(n log n)，在最佳情况下，基准能有效地将数组分成两部分。

快速排序的优点：

  • 平均情况下，快速排序的时间复杂度为O(n log n)，比冒泡排序、选择排序等O(n²)的算法要高效。
  • 排序过程中使用了分治思想，数据交换频繁，性能优于其他简单的排序算法。

注意：

  • 快速排序在某些极端情况下，性能可能退化为O(n²)，尤其当数组本身是已经有序的，或者每次选取的基准元素不合适时。
  • 对于较小的数组，快速排序的递归和交换可能导致性能下降，此时使用插入排序可能更好。

总结与建议

常见排序算法对比：

排序算法 最坏时间复杂度 平均时间复杂度 最好时间复杂度 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定
插入排序 O(n²) O(n²) O(n) O(1) 稳定
快速排序 O(n²) O(n log n) O(n log n) O(log n) 不稳定

推荐：

  • 对于小型数组，插入排序较为高效。
  • 对于大部分无序数组，快速排序通常是首选算法，它的时间复杂度较低，尤其适用于较大的数据集。
  • 如果数据较为接近有序，或者是部分有序，可以考虑使用插入排序来优化性能。
  • 冒泡排序和选择排序的效率较低，通常仅在学习算法时使用，实际应用中不推荐使用这两种排序算法。

结构体排序