AP 計算機科學/排序
排序和搜尋是計算機科學中兩個常用的操作。在 AP 考試中，你需要了解某些透過集合進行排序的方法，稱為排序演算法，以及某些在集合中搜索給定專案的 方法，稱為搜尋演算法。
有許多常用的演算法用於對集合進行排序。以下是一些重要的演算法
選擇排序是一種迭代排序演算法，它使用“搜尋和交換”方法對集合進行排序。對於對集合的每一次遍歷，演算法會找到要排序的最小元素，並將其與集合中的第一個未排序元素交換。演算法以這種方式繼續，找到集合中下一個最小的元素，並將其與下一個未排序元素交換。最後，當只剩下兩個未排序元素時，它們會被比較（如果有必要則交換），排序完成。
選擇排序演算法的效率和比較次數並不取決於集合中元素的初始順序；無論初始順序如何，比較次數都是相同的。對於包含n個元素的集合，集合在經過n-1次遍歷後會完成排序。在第k次遍歷後，前k個元素會完成排序，並且會放置到它們最終的排序位置。在第k次遍歷中，會進行n-k次比較。排序完成後，進行的比較總數是n(n-1)/2。選擇排序演算法在最優、平均和最差情況下都具有O(n2)的效率。換句話說，選擇排序沒有最優或最差情況；每種情況都被認為是平均情況。
插入排序也是一種迭代排序演算法。使用這種演算法時，第一個元素相對於它本身是“排序的”。然後演算法取第二個元素，並將其與第一個元素進行比較，如果需要，將其插入到第一個元素之前。從這一點開始，演算法取下一個未排序元素，並將其與排序後的元素進行比較，根據需要將元素插入到正確的位置。演算法以這種方式繼續，根據需要移動排序後的元素，以便為要插入的下一個元素騰出空間。
插入排序演算法的效率和比較次數確實取決於集合中元素的初始順序。對於包含n個元素的陣列，陣列在經過n-1次遍歷後會完成排序。效率在最優、平均和最差情況下有所不同。
- 插入排序的最佳情況是如果集合一開始就已經按順序排序。對陣列的每一次遍歷只需要進行一次比較，這會表明正在比較的元素相對於排序後的列表已經是它正確的位置。不需要移動任何元素。進行的比較總數是(n-1)。在這種情況下，插入排序演算法具有O(n)的效率。
- 插入排序的最差情況是如果集合最初是按逆序排序的，這會導致需要進行最大可能的比較和移動次數來對集合進行排序。在第k次遍歷後，前k+1個元素會相對於彼此進行排序，但不會放置到它們最終的排序位置。在第k次遍歷中，會進行k次比較。排序完成後，進行的比較總數是n(n-1)/2。在這種情況下，插入排序演算法具有O(n2)的效率。
歸併排序是一種遞迴演算法，它使用“分治”方法對集合進行排序。演算法每次被呼叫時，都會檢查集合中是否有多於一個元素，如果有多於一個元素，則集合會被“拆分”成兩半。如果元素數量為偶數，則兩半相等，但如果元素數量為奇數，則左半部分將包含比右半部分多一個元素。此時，演算法會使用遞迴，先呼叫自身對集合的左半部分進行歸併排序，然後對右半部分進行歸併排序。當演算法呼叫自身對其中一半進行歸併排序時，它會再次將一半“拆分”成兩半，然後呼叫自身對每半進行排序。這個過程會不斷重複，直到整個集合被“拆分”成單個元素，或長度為 1 的子集合。當方法呼叫自身對其中一個進行排序時，初始測試會檢查子集合中是否有多於一個元素，如果只有一個元素，則測試會失敗，因為子集合中只有一個元素。這就是遞迴停止的地方，演算法會返回到對一半進行排序，方法是比較兩個相鄰元素，對它們進行排序，然後將它們重新組合成一個排序後的子集合。這個過程會不斷重複，直到所有單個元素都被排序並重新組合成排序後的子集合。然後，子集合本身會被比較、排序和重新組合。這個過程會不斷重複，直到子集合被重新組合，形成兩個排序後的半部分。最後，左半部分和右半部分會相互比較、排序和重新組合，建立最終的、完全排序後的集合。
以下是對歸併排序演算法的偽程式碼表示
If there is more than one element in the collection
Break the collection into two halves
Mergesort the left half
Mergesort the right half
Compare the two halves
Merge the two subcollections into a sorted collection
歸併排序的效率不受元素初始排序的影響。因為歸併排序需要使用與要排序的集合一樣大的臨時集合，所以如果可用記憶體空間有限，就不應該使用這種演算法。這種演算法由多個部分組成
- 演算法中將子集合合併的部分首先比較子集合中的每個元素，這是一個O(n)過程，然後將元素從臨時集合複製回原始集合，這也是一個O(n)過程。這使得演算法的實際合併需要總共2n個操作，使得演算法的這部分成為一個O(n)過程。（請記住，在 Big-O 符號中會忽略常數。）
- 將包含n個元素的集合拆分成n個包含一個元素的子集合需要log2n次劃分，這是一個O(logn)過程。
請記住，對於集合每一次劃分成子集合，必須呼叫演算法的合併部分。這使得歸併排序演算法在最優、平均和最差情況下都具有O(nlogn)的效率。換句話說，沒有最優或最差情況，因為每種情況都被認為是平均情況。
快速排序平均而言是用於對包含大量元素的集合進行排序的最快排序演算法。快速排序是遞迴的，並且還使用“分治”方法進行排序。這種演算法首先透過對集合進行分割槽，選擇一個樞紐點，通常是集合中的第一個元素或隨機選擇的元素，然後將所有小於樞紐點值的所有元素移動到樞紐點的左側，並將所有大於或等於樞紐點值的所有元素移動到樞紐點的右側。然後演算法使用遞迴，將陣列分成兩半，並呼叫自身對每半進行快速排序。最後，當每個元素都被移動到它正確的位置時，排序完成。
以下是對快速排序演算法的偽程式碼表示
If there are at least two elements in the collection
Partition the collection
Quicksort the left collection
Quicksort the right collection
線性搜尋 涉及遍歷集合中的每個元素，直到找到所需的值。這通常使用簡單的 for 迴圈實現，從索引 0 開始，一直計數到集合的最後一個索引。這是最簡單的搜尋方法，但如果集合非常大，其效率就會降低。
二分搜尋 涉及遍歷集合並比較中間索引與目標值。這需要一個排序後的集合才能起作用。
例如：您要在一個包含 100 個整數的陣列中找到數字 12，陣列中的值等於索引加 1（1,2,3,4,5,..,99,100）。請注意，此陣列已排序，最小的值在左側，最大的值在右側。您將比較中間值（50）與搜尋值（12）。由於 50>12，您將排除所有從 50 到 100 的值，因為它們也都大於搜尋值。然後您將檢查 25 與搜尋值，因為這是 49 到 1 之間的新的中間值。同樣，此值大於搜尋詞，因此所有數字 25 到 49 都被排除。此過程將繼續，直到您最終得到 12 作為中間值。