This is a beta course, so its structure, chapters, and examples may continue to change.

Selection Sort

Idea

Selection Sort repeatedly picks the minimum (or maximum) from the unsorted part and places it at the end of the sorted part until done.

选择排序

点击“执行一步”观察算法状态变化。

In each pass, find the minimum in the unsorted part and swap with its first element.
Repeat $n-1$ passes until fully sorted.

Pseudo-code:

for i = 0 to n-2:
    min = i
    for j = i+1 to n-1:
        if A[j] < A[min]:
            min = j
    if min != i:
        swap(A[i], A[min])

Run selection sort on $A = [64, 25, 12, 22, 11]$ and show each pass.

参考答案

思路：每趟选最小放前。

步骤：

答案：如上，每趟最小归位。

What are the time and space complexities of selection sort?

参考答案

思路：复杂度与空间。

步骤：

答案：时间 $O(n^2)$ ，空间 $O(1)$ 。