47. 若我們的資料尚未收集完成，可能陸陸續續有資料進來，這種情況下適合哪種排序法？
(A) Quick sort
(B) Merge sort
(C) Insertion sort
(D) Selection sort

當資料尚未收集完成，並且可能陸陸續續有新資料進來時，我們需要一種能夠有效處理「增量式」排序需求的演算法。這種情況下，演算法應該能夠將新到達的資料有效率地插入到已經排序好的序列中，而不需要重新排序整個資料集。

讓我們分析各個排序法：

• (A) 快速排序（Quick Sort）：

  • 這是一種基於分治（divide-and-conquer）策略的演算法，通常在處理整個、已知的資料集時非常高效（平均時間複雜度為 O(n log n)）。
  • 它不適合用於資料持續進入的情況，因為它需要對整個資料集進行分區和遞迴處理。

• (B) 合併排序（Merge Sort）：

  • 這也是一種分治演算法，同樣在處理整個資料集時表現良好（時間複雜度為 O(n log n)）。
  • 它也不適合增量式數據，因為它涉及到將子列表合併的過程，不適合即時將新資料插入。

• (C) 插入排序（Insertion Sort）：

  • 這是一種簡單的排序演算法，它將每個新元素插入到已排序序列的正確位置。
  • 它的核心思想是將一個未排序的元素插入到一個已經排序好的子陣列中。
  • 非常適合資料陸續進來的情況。當新資料到達時，你可以將其視為一個新的元素，然後使用插入排序的邏輯將其插入到已經排序好的部分中，而無需重新排序所有舊資料。
  • 儘管其最壞時間複雜度為 O(n^2)，但在處理小規模數據或增量式數據時（當每次插入操作的資料量較小時），它的表現相當不錯。

• (D) 選擇排序（Selection Sort）：

  • 這是一種每次迭代都找出未排序部分中的最小（或最大）元素，然後將其放到已排序部分末尾的演算法。
  • 它不適合資料持續進入的情況，因為每次都需要掃描未排序的整個部分來找到最小值，效率不高。

因此，如果資料是陸陸續續進來的，最適合的排序法是插入排序。