利用循環遍歷來判斷是否相等

二分查找/折半查找

前提條件：數組中的數據有序

每次排除一般的查找范圍

用min,max,mid來處理，最大加最小除2，比較，然后得到在中間左邊還是右邊然后更新最大最小

public class Two {// 二分查找方法，返回目標值在數組中的索引，如果未找到則返回 -1public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {// 計算中間索引int mid = left + (right - left) / 2;if (arr[mid] == target) {// 找到目標值，返回中間索引return mid;} else if (arr[mid] < target) {// 目標值在右半部分，更新左邊界left = mid + 1;} else {// 目標值在左半部分，更新右邊界right = mid - 1;}}// 未找到目標值，返回 -1return -1;}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13};int target = 7;// 調用二分查找方法int result = binarySearch(arr, target);if (result != -1) {System.out.println("目標值 " + target + " 在數組中的索引是: " + result);} else {System.out.println("目標值 " + target + " 不在數組中。");}}
}

插值查找

和二分查找差不多但是計算mid方式不同，前提是數組數據分布均勻

斐波那契查找

黃金比例又稱黃金分割，是指事物各部分間一定的數學比例關系，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比，其比值約為1:0.618或1.618:1。

分塊查找

原則：前一塊中的最大數據，小于后一塊中所有的數據；塊數數量一般等于數組的個數開根號。

先確定要查找的元素在哪一塊，然后在塊內挨個查找

哈希查找

哈希查找是分塊查找的進階版，適用于數據一邊添加一邊查找的情況。

一般是數組 + 鏈表的結合體或者是數組+鏈表 + 紅黑樹的結合體

樹表查找

二叉查找樹是先對待查找的數據進行生成樹，確保樹的左分支的值小于右分支的值，然后在就行和每個節點的父節點比較大小，查找最適合的范圍。 這個算法的查找效率很高，但是如果使用這種查找方法要首先創建樹。

排序算法

冒泡排序

冒泡排序（Bubble Sort）是一種簡單的排序算法，它通過重復地遍歷待排序的列表，比較相鄰的元素并交換它們的位置來實現排序。該算法的名稱來源于較小的元素會像"氣泡"一樣逐漸"浮"到列表的頂端。

比較相鄰元素：從列表的第一個元素開始，比較相鄰的兩個元素。

交換位置：如果前一個元素比后一個元素大，則交換它們的位置。

重復遍歷：對列表中的每一對相鄰元素重復上述步驟，直到列表的末尾。這樣，最大的元素會被"冒泡"到列表的最后。

縮小范圍：忽略已經排序好的最后一個元素，重復上述步驟，直到整個列表排序完成。

選擇排序

選擇排序（Selection Sort）是一種簡單直觀的排序算法，無論什么數據進去都是 O(n2) 的時間復雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。

選擇排序基本思想是每次從待排序的數據中選擇最小（或最大）的元素，放到已排序序列的末尾，直到全部數據排序完成。

初始化：將列表分為已排序部分和未排序部分。初始時，已排序部分為空，未排序部分為整個列表。

查找最小值：在未排序部分中查找最小的元素。

交換位置：將找到的最小元素與未排序部分的第一個元素交換位置。

更新范圍：將未排序部分的起始位置向后移動一位，擴大已排序部分的范圍。

重復步驟：重復上述步驟，直到未排序部分為空，列表完全有序。

插入排序

插入排序（Insertion Sort）是一種簡單直觀的排序算法，它的工作原理類似于整理撲克牌。

插入排序通過構建有序序列，對于未排序的數據，在已排序序列中從后向前掃描，找到相應位置并插入。

插入排序的代碼實現雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。

插入排序和冒泡排序一樣，也有一種優化算法，叫做拆半插入。

初始化：將列表分為已排序部分和未排序部分。初始時，已排序部分只包含第一個元素，未排序部分包含剩余元素。

選擇元素：從未排序部分中取出第一個元素。

插入到已排序部分：將該元素與已排序部分的元素從后向前依次比較，找到合適的位置插入。

重復步驟：重復上述步驟，直到未排序部分為空，列表完全有序。

快速排序

快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。

選擇基準元素：從列表中選擇一個元素作為基準（pivot）。選擇方式可以是第一個元素、最后一個元素、中間元素或隨機元素。

分區：將列表重新排列，使得所有小于基準元素的元素都在基準的左側，所有大于基準元素的元素都在基準的右側。基準元素的位置在分區完成后確定。

遞歸排序：對基準元素左側和右側的子列表分別遞歸地進行快速排序。

合并：由于分區操作是原地進行的，遞歸結束后整個列表已經有序。

希爾排序

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。

選擇增量序列：選擇一個增量序列（gap sequence），用于將列表分成若干子列表。常見的增量序列有希爾增量（n/2, n/4, ..., 1）等。

分組插入排序：按照增量序列將列表分成若干子列表，對每個子列表進行插入排序。

縮小增量：逐步縮小增量，重復上述分組和排序過程，直到增量為 1。

最終排序：當增量為 1 時，對整個列表進行一次插入排序，完成排序。

歸并排序

歸并排序的核心思想是將一個大問題分解成若干個小問題，分別解決這些小問題，然后將結果合并起來，最終得到整個問題的解。具體到排序問題，歸并排序的步驟如下：

分解（Divide）：將待排序的數組分成兩個子數組，每個子數組包含大約一半的元素。

解決（Conquer）：遞歸地對每個子數組進行排序。

合并（Combine）：將兩個已排序的子數組合并成一個有序的數組。

通過不斷地分解和合并，最終整個數組將被排序。

申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；

設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

重復步驟 3 直到某一指針達到序列尾；

將另一序列剩下的所有元素直接復制到合并序列尾。

堆排序

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

1. 大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；
2. 小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

堆排序的平均時間復雜度為 Ο(nlogn)。

創建一個堆 H[0……n-1]；

把堆首（最大值）和堆尾互換；

把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數組頂端數據調整到相應位置；

重復步驟 2，直到堆的尺寸為 1。

計數排序

計數排序（Counting Sort）是一種非比較型的排序算法，適用于對整數或有限范圍內的數據進行排序。它的核心思想是通過統計每個元素的出現次數，然后根據統計結果將元素放回正確的位置。計數排序的時間復雜度為 O(n + k)，其中 n 是待排序元素的數量，k 是數據的范圍大小。

計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

當輸入的元素是 n 個 0 到 k 之間的整數時，它的運行時間是 Θ(n + k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來計數的數組C的長度取決于待排序數組中數據的范圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于數據范圍很大的數組，需要大量時間和內存。例如：計數排序是用來排序0到100之間的數字的最好的算法，但是它不適合按字母順序排序人名。但是，計數排序可以用在基數排序中的算法來排序數據范圍很大的數組。

統計頻率：遍歷待排序的列表，統計每個元素出現的次數，存儲在一個計數數組中。

累加頻率：將計數數組中的值累加，得到每個元素在排序后列表中的最后一個位置。

構建有序列表：遍歷待排序的列表，根據計數數組中的位置信息，將元素放到正確的位置。

輸出結果：將排序后的列表輸出。

桶排序

桶排序（Bucket Sort）是一種分布式排序算法，它將待排序的元素分配到若干個桶（Bucket）中，然后對每個桶中的元素進行排序，最后將所有桶中的元素按順序合并。桶排序的核心思想是將數據分到有限數量的桶中，每個桶再分別排序（可以使用其他排序算法或遞歸地使用桶排序）。

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點：

在額外空間充足的情況下，盡量增大桶的數量

使用的映射函數能夠將輸入的 N 個數據均勻的分配到 K 個桶中

同時，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關重要。

初始化桶：根據數據的范圍和分布，創建若干個桶。

分配元素：遍歷待排序的列表，將每個元素分配到對應的桶中。

排序每個桶：對每個桶中的元素進行排序（可以使用插入排序、快速排序等）。

合并桶：將所有桶中的元素按順序合并，得到最終排序結果。

基數排序

基數排序（Radix Sort）是一種非比較型的排序算法，它通過逐位比較元素的每一位（從最低位到最高位）來實現排序。基數排序的核心思想是將整數按位數切割成不同的數字，然后按每個位數分別進行排序。基數排序的時間復雜度為 O(n * k)，其中 n 是列表長度，k 是最大數字的位數。

確定最大位數：找到列表中最大數字的位數，確定需要排序的輪數。

按位排序：從最低位開始，依次對每一位進行排序（通常使用計數排序或桶排序作為子排序算法）。

合并結果：每一輪排序后，更新列表的順序，直到所有位數排序完成。

這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異：

基數排序：根據鍵值的每位數字來分配桶；

計數排序：每個桶只存儲單一鍵值；

桶排序：每個桶存儲一定范圍的數值；