# 🔎 搜尋與排序 --- - **學習目標：** - 了解搜尋與排序的基本演算法 - 學會線性搜尋與二分搜尋 - 學會冒泡排序、插入排序、快速排序 - 能進行時間複雜度分析 (Big-O) --- ## 🔖 為什麼需要搜尋與排序？ - **搜尋 (Search)**：在資料集合中找出指定元素 - **排序 (Sort)**：將資料按照一定順序排列 - 這些都是演算法的基礎，許多進階資料結構（例如樹、雜湊表）都依賴它們 --- ### [線性搜尋（Linear Search）]((https://www.cs.usfca.edu/~galles/visualization/Search.html)) - 從頭到尾逐一檢查 - 適合小型或未排序資料 ```cpp int linearSearch(int arr[], int n, int target) { for(int i=0; i<n; i++) if(arr[i] == target) return i; return -1; // 沒找到 } ``` - 時間複雜度: O(n) --- ### [二分搜尋（Binary Search）](https://www.cs.usfca.edu/~galles/visualization/Search.html) - 針對 已排序陣列 - 每次將搜尋區間砍半 → 高效率 - 時間複雜度: O(log n) ```cpp int binarySearch(int arr[], int n, int target) { int left = 0, right = n-1; while(left <= right) { int mid = (left + right) / 2; if(arr[mid] == target) return mid; else if(arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } ``` --- ## [排序演算法](https://visualgo.net/en/sorting)介紹 - 冒泡排序（Bubble Sort） - 插入排序（Insertion Sort） - 快速排序（Quick Sort） - 合併排序 （merge Sort） - Heap Sort --- ### 冒泡排序（Bubble Sort） - 每回合比較相鄰兩元素，若逆序則交換 - 時間複雜度：O(n^2) ```cpp void bubbleSort(int arr[], int n) { for(int i=0; i<n-1; i++) { for(int j=0; j<n-1-i; j++) { if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]); } } } ``` --- ### 插入排序（Insertion Sort） - 每次將新元素插入到已排序序列的正確位置 - 適合小規模或接近有序的資料 - 時間複雜度：O(n^2) ```cpp 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; } } ``` --- ### 快速排序（Quick Sort） - 分治法（Divide and Conquer） - 選擇基準（pivot），將陣列分為左右兩部分再遞迴排序 - 平均時間複雜度：O(n log n) - 最差情況：O(n^2) ```cpp 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++; swap(arr[i], arr[j]); } } swap(arr[i+1], arr[high]); 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); } } ``` --- ### 合併排序（Merge Sort） - 分治法（Divide and Conquer） - 將陣列不斷分割，再合併排序好的子陣列 - 時間複雜度：**最佳 / 平均 / 最差 = O(n log n)** - 穩定排序（不會改變相同元素的相對位置） ```cpp void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1, n2 = r - m; vector<int> L(n1), R(n2); for(int i=0; i<n1; i++) L[i] = arr[l+i]; for(int j=0; j<n2; j++) R[j] = arr[m+1+j]; int i=0, j=0, k=l; while(i<n1 && j<n2) { if(L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } while(i<n1) arr[k++] = L[i++]; while(j<n2) arr[k++] = R[j++]; } void mergeSort(int arr[], int l, int r) { if(l < r) { int m = l + (r-l)/2; mergeSort(arr, l, m); mergeSort(arr, m+1, r); merge(arr, l, m, r); } } ``` --- ### 📊 時間複雜度分析 (Big-O) | 演算法 | 最佳情況 | 平均情況 | 最差情況 | | -------- |:---------- |:---------- | ---------- | | 線性搜尋 | O(1) | O(n) | O(n) | | 二分搜尋 | O(1) | O(log n) | O(log n) | | 冒泡排序 | O(n) | O(n^2) | O(n^2) | | 插入排序 | O(n) | O(n^2) | O(n^2) | | 快速排序 | O(n log n) | O(n log n) | O(n^2) | | 合併排序 | O(n log n) | O(n log n) | O(n log n) | --- ## Asymptotic Notation --- ### Θ-Notation, asymptotic tight bound  ---- - For insertion sort, the worst case is `O(n)`, best case is `linear time`. - i.e., Θ(n) is not appropriate to describe the time complexity of the insertion sort. --- ### O-Notation, asymptotic upper bound  ---- - O(n) best describes time required for insertion sort - What about binary search? --- ## Thinking 1. quicksort 2. mergesort --- ## 🛠️ 課堂練習 (Lab) - 練習一： - 實作一個 linearSearch 與 binarySearch，比較在 10000 筆資料下的速度差異。 --- ## 💡 本週作業 - 用 linked list 撰寫 mergesort. - Explain the time complexity of the above mergesort.