查找

順序查找（線性查找）

算法思想：

從數組的第一個元素開始，逐個與目標值進行比較，直到找到目標值或查找完整個數組。

時間復雜度：

• 最好情況：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;
  }