查找

顺序查找（线性查找）

算法思想：

从数组的第一个元素开始，逐个与目标值进行比较，直到找到目标值或查找完整个数组。

时间复杂度：

• 最好情况：O(1)（目标在第一个位置）
• 最坏情况：O(n)
• 平均情况：O(n)

适用场景：

适用于无序数组或链表。

#include <stdio.h>int linearSearch(int arr[], int n, int target) {for (int i = 0; i < n; i++) {if (arr[i] == target)return i;  // 找到，返回索引}return -1;  // 未找到
}int main() {int arr[] = {5, 3, 8, 4, 2};int n = sizeof(arr) / sizeof(arr[0]);int target = 4;int index = linearSearch(arr, n, target);if (index != -1)printf("元素在索引 %d\n", index);elseprintf("未找到元素\n");return 0;
}

二分查找（折半查找）

算法思想：

在有序数组中查找目标值。每次将查找区间缩小一半，通过比较中间值与目标值的大小来决定下一步查找区间。

时间复杂度：

• O(log n)

适用场景：

适用于有序数组。

C 语言实现（递归和非递归）：

#include <stdio.h>// 非递归实现
int binarySearch(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target)return mid;else if (arr[mid] < target)left = mid + 1;elseright = mid - 1;}return -1;
}// 递归实现
int binarySearchRecursive(int arr[], int left, int right, int target) {if (left > right) return -1;int mid = left + (right - left) / 2;if (arr[mid] == target)return mid;else if (arr[mid] < target)return binarySearchRecursive(arr, mid + 1, right, target);elsereturn binarySearchRecursive(arr, left, mid - 1, target);
}int main() {int arr[] = {2, 3, 4, 5, 8};int n = sizeof(arr) / sizeof(arr[0]);int target = 5;int index = binarySearch(arr, 0, n - 1, target);if (index != -1)printf("元素在索引 %d\n", index);elseprintf("未找到元素\n");return 0;
}

---

插值查找

算法思想：

是对二分查找的改进，根据目标值与数组两端值的差距来估算中间点的位置，适用于数据分布均匀的有序数组。

时间复杂度：

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

C 语言实现：

int interpolationSearch(int arr[], int left, int right, int target) {while (left <= right && arr[left] != arr[right]) {int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);if (arr[pos] == target)return pos;else if (arr[pos] < target)left = pos + 1;elseright = pos - 1;}if (left <= right && arr[left] == target)return left;return -1;
}

---

排序

冒泡排序（Bubble Sort）

原理： 冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。

• 时间复杂度：

  • 最好情况：O(n) （当输入数组已经是排序好的）
  • 平均和最坏情况：O(n^2)

• 稳定性： 稳定

• 适用场景： 数据量较小或基本有序的数据集

•  语言代码：

  #include <stdio.h>void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int swapped = 0;for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = 1;}}if (!swapped) break;  // 如果本轮没有交换，说明已经有序}
  }int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);printf("排序后的数组：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");return 0;
  }

选择排序（Selection Sort）

原理： 选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完为止。

• 时间复杂度：

  • 最好、平均和最坏情况：O(n^2)

• 稳定性： 不稳定

• 适用场景： 小规模数据集

语言代码：

#include <stdio.h>void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex])minIndex = j;}// 交换最小值和当前第一个未排序元素int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}
}int main() {int arr[] = {64, 25, 12, 22, 11};int n = sizeof(arr) / sizeof(arr[0]);selectionSort(arr, n);printf("排序后的数组：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

插入排序（Insertion Sort）

原理： 插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因此空间复杂度为O(1)。

• 时间复杂度：

  • 最好情况：O(n) （输入数组已经是排序好的）
  • 平均和最坏情况：O(n^2)

• 稳定性： 稳定

• 适用场景： 小规模或者基本有序的数据

  语言代码：

  #include <stdio.h>void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
  }int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);insertionSort(arr, n);printf("排序后的数组：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");return 0;
  }

快速排序（Quick Sort）

原理： 快速排序使用分治法策略来把一个序列分成较小和较大的两个子序列，然后递归地排序两个子序列。具体来说，选择一个基准元素，通常选择第一个元素或者最后一个元素，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

• 时间复杂度：

  • 最好和平均情况：O(n log n)
  • 最坏情况：O(n^2) （例如，当每次选取的基准都是当前序列中的最小或最大值时）

• 稳定性： 不稳定

  语言代码：

  #include <stdio.h>int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;
  }void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
  }int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("排序后的数组：\n");for (int i = 0; i < n; i++)printf("%d ", arr[i]);printf("\n");return 0;
  }