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 作为中间值。