95. 若將資料儲存在一個陣列中，以快速排序(quick sort) 演算法將資料由小排到大，並以序列的第 1 筆資料作為 比較的樞紐值(pivot)。請問包含 7 筆資料的情況下，以 下哪個資料序列對執行快速排序演算法是最差的情況 (需要遞迴執行最多次)?
(A) 4, 3, 2, 1, 6, 7, 5
(B) 4, 2, 3, 1, 6, 5, 7
(C) 5, 2, 1, 4, 3, 6, 7
(D) 1, 2, 3, 4, 5, 6, 7

要判斷哪種資料序列對於快速排序演算法（以序列的第一筆資料作為樞紐值）是最差的情況，我們需要理解快速排序的遞迴特性。

快速排序的效率很大程度上取決於樞紐值 (pivot) 的選擇。

• 最佳情況： 樞紐值能將序列均勻地分成兩半，每次遞迴處理的子問題大小約為原來的一半。這樣遞迴深度最小（O(logn)），總時間複雜度為 O(nlogn)。
• 最差情況： 樞紐值每次都選擇到序列中的最大值或最小值。這會導致每次分割都產生一個空子序列和一個包含所有其他元素的子序列。這種情況下，遞迴深度會達到 O(n)，使得總時間複雜度退化到 O(n2)。

題目中明確指出，以序列的第 1 筆資料作為比較樞紐值。因此，最差的情況就是每次選取的第一筆資料都是當前子序列的最大值或最小值。

讓我們來分析每個選項：

• (A) 4, 3, 2, 1, 6, 7, 5

  • 第一次遞迴：Pivot = 4。分割後左邊是 [3, 2, 1]，右邊是 [6, 7, 5]。
  • 雖然左邊是降序，但右邊不是完全升序，不會是每次都選到最大或最小值。

• (B) 4, 2, 3, 1, 6, 5, 7

  • 第一次遞迴：Pivot = 4。分割後左邊是 [2, 3, 1]，右邊是 [6, 5, 7]。
  • 同樣，不會是每次都選到最大或最小值。

• (C) 5, 2, 1, 4, 3, 6, 7

  • 第一次遞迴：Pivot = 5。分割後左邊是 [2, 1, 4, 3]，右邊是 [6, 7]。
  • 雖然不是最差，但也不是最佳。

• (D) 1, 2, 3, 4, 5, 6, 7

  • 第一次遞迴：Pivot = 1。
    • Pivot 1 是當前序列的最小值。
    • 分割後，左邊是空序列，右邊是 [2, 3, 4, 5, 6, 7]。
  • 第二次遞迴：處理 [2, 3, 4, 5, 6, 7]。Pivot = 2。
    • Pivot 2 是當前序列的最小值。
    • 分割後，左邊是空序列，右邊是 [3, 4, 5, 6, 7]。
  • 這個模式會一直持續下去：每次遞迴都選到當前子序列的最小值作為樞紐值，導致每次分割都只「淘汰」一個元素，且產生一個空子序列和一個大小減一的子序列。
  • 這種情況下，需要進行 N 次遞迴（N 為資料筆數），這是最差的情況。

因此，對於以第一筆資料作為樞紐值的快速排序，完全升序或完全降序的序列會導致最差的性能。

The final answer is D​