選擇排序

習題預習

1. Selection Sort是什麼排序演算法？它是如何運作的？
2. 在Selection Sort中，對於n個元素的未排序子數列，需要執行多少次比較操作和交換操作？
3. Selection Sort和Bubble Sort之間有什麼差異？哪個演算法的效率更高？
4. 在Selection Sort中，當要將一個元素插入到已排序子數列中時，是從哪個方向開始執行比較操作？
5. 如果要對一個數組進行升序排序，什麼情況下會選擇使用Selection Sort？

說明知識

Selection Sort（選擇排序）是一種簡單的排序演算法，它會選擇最小的元素在整個序列中，將其與序列中的第一個元素交換，然後在剩餘的元素中選擇最小的元素，將其與序列中的第二個元素交換，以此類推，直到整個序列都被排序過。

下面是一個實現 Selection Sort 的 Python 程序：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

該程序使用雙重循環，外部循環用於遍歷序列中的每一個元素，內部循環用於查找最小的元素。在每次內部循環結束時，我們找到了最小的元素，並且將其移動到序列的開頭。

舉個例子，假設我們要對以下整數序列進行 Selection Sort 操作：

[64, 25, 12, 22, 11]

首先，我們找到最小的元素 11，然後將其與序列的第一個元素 64 交換，序列變成：

[11, 25, 12, 22, 64]

然後，我們從第二個元素 25 到最後一個元素 64 中找到最小的元素 12，然後將其與序列的第二個元素 25 交換，序列變成：

[11, 12, 25, 22, 64]

然後，繼續進行類似的操作，直到整個序列都被排序過：

[11, 12, 22, 25, 64]

因此，根據上面的算法，我們在 $O(n^2)$ 的時間複雜度內將序列進行了排序。

彙總重點

Selection Sort的重點如下：

1. 从未排序的数据中选出最小值，将其放到已排序的数据末尾，重复这个过程直到所有数据都已排序。

2. 和其他排序算法一样，Selection Sort的时间复杂度为O(n^2)。

3. Selection Sort是一个in-place算法，使用的空间不随n的大小而改变。

4. 因为Selection Sort在每次查找过程中只找到一个最小值，所以这个算法非常适用于处理小数据集。

5. 和Bubble Sort相比，Selection Sort在大数据集上表现更加稳定。

6. 在已经排好序的数组中，Selection Sort的时间复杂度仍然为O(n^2)。

7. Selection Sort的平均复杂度为 O(n^2)。

8. 在任何情况下，Selection Sort的交换次数最多只有n-1次。

知識測驗

1. 如何將Selection Sort改為遞增排序？

答案：只需要在交換兩個元素的地方進行細微更改即可。原本的比較操作應該是if (arr[j] > arr[min_idx])，將其改為if (arr[j] < arr[min_idx])即可。

2. Selection Sort每次交換的次數是多少？

答案：Selection Sort每次可以找到當前最小元素並將其放入正確的位置，這需要進行一次交換。因此，它需要進行n-1次交換。

3. 如果Selection Sort的輸入列表只有一個元素，它能正確地排序嗎？

答案：是的，輸入列表只有一個元素的情況下，該元素已經處於正確位置，因此Selection Sort不需要執行任何操作。

4. 如何優化Selection Sort的效率？

答案：可以將當前最小元素的位置存儲在變量min_idx中，以避免在每次交換時查找最小元素。此外，可以在某些情況下停止排序，例如當列表已經有序時。

5. 與其他排序算法相比，Selection Sort的時間複雜度是什麼？

答案：Selection Sort的時間複雜度是O(n^2)，與其他簡單的排序算法如Bubble Sort和Insertion Sort相同。然而，比較複雜的排序算法如Quick Sort和Merge Sort的時間複雜度要小得多。