11.2   Selection sort

Selection sort works on a very simple principle: it starts a loop where each iteration selects the smallest element from the unsorted interval and moves it to the end of the sorted interval.

Suppose the length of the array is \(n\), the algorithm flow of selection sort is as shown in Figure 11-2.

1. Initially, all elements are unsorted, i.e., the unsorted (index) interval is \([0, n-1]\).
2. Select the smallest element in the interval \([0, n-1]\) and swap it with the element at index \(0\). After this, the first element of the array is sorted.
3. Select the smallest element in the interval \([1, n-1]\) and swap it with the element at index \(1\). After this, the first two elements of the array are sorted.
4. Continue in this manner. After \(n - 1\) rounds of selection and swapping, the first \(n - 1\) elements are sorted.
5. The only remaining element is necessarily the largest element and does not need sorting, thus the array is sorted.

<1><2><3><4><5><6><7><8><9><10><11>

Figure 11-2   Selection sort process

In the code, we use \(k\) to record the smallest element within the unsorted interval:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

selection_sort.py

def selection_sort(nums: list[int]):
    """选择排序"""
    n = len(nums)
    # 外循环：未排序区间为 [i, n-1]
    for i in range(n - 1):
        # 内循环：找到未排序区间内的最小元素
        k = i
        for j in range(i + 1, n):
            if nums[j] < nums[k]:
                k = j  # 记录最小元素的索引
        # 将该最小元素与未排序区间的首个元素交换
        nums[i], nums[k] = nums[k], nums[i]

selection_sort.cpp

/* 选择排序 */
void selectionSort(vector<int> &nums) {
    int n = nums.size();
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        swap(nums[i], nums[k]);
    }
}

selection_sort.java

/* 选择排序 */
void selectionSort(int[] nums) {
    int n = nums.length;
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

selection_sort.cs

/* 选择排序 */
void SelectionSort(int[] nums) {
    int n = nums.Length;
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        (nums[k], nums[i]) = (nums[i], nums[k]);
    }
}

selection_sort.go

/* 选择排序 */
func selectionSort(nums []int) {
    n := len(nums)
    // 外循环：未排序区间为 [i, n-1]
    for i := 0; i < n-1; i++ {
        // 内循环：找到未排序区间内的最小元素
        k := i
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[k] {
                // 记录最小元素的索引
                k = j
            }
        }
        // 将该最小元素与未排序区间的首个元素交换
        nums[i], nums[k] = nums[k], nums[i]

    }
}

selection_sort.swift

/* 选择排序 */
func selectionSort(nums: inout [Int]) {
    // 外循环：未排序区间为 [i, n-1]
    for i in nums.indices.dropLast() {
        // 内循环：找到未排序区间内的最小元素
        var k = i
        for j in nums.indices.dropFirst(i + 1) {
            if nums[j] < nums[k] {
                k = j // 记录最小元素的索引
            }
        }
        // 将该最小元素与未排序区间的首个元素交换
        nums.swapAt(i, k)
    }
}

selection_sort.js

/* 选择排序 */
function selectionSort(nums) {
    let n = nums.length;
    // 外循环：未排序区间为 [i, n-1]
    for (let i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        let k = i;
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[k]) {
                k = j; // 记录最小元素的索引
            }
        }
        // 将该最小元素与未排序区间的首个元素交换
        [nums[i], nums[k]] = [nums[k], nums[i]];
    }
}

selection_sort.ts

/* 选择排序 */
function selectionSort(nums: number[]): void {
    let n = nums.length;
    // 外循环：未排序区间为 [i, n-1]
    for (let i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        let k = i;
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[k]) {
                k = j; // 记录最小元素的索引
            }
        }
        // 将该最小元素与未排序区间的首个元素交换
        [nums[i], nums[k]] = [nums[k], nums[i]];
    }
}

selection_sort.dart

/* 选择排序 */
void selectionSort(List<int> nums) {
  int n = nums.length;
  // 外循环：未排序区间为 [i, n-1]
  for (int i = 0; i < n - 1; i++) {
    // 内循环：找到未排序区间内的最小元素
    int k = i;
    for (int j = i + 1; j < n; j++) {
      if (nums[j] < nums[k]) k = j; // 记录最小元素的索引
    }
    // 将该最小元素与未排序区间的首个元素交换
    int temp = nums[i];
    nums[i] = nums[k];
    nums[k] = temp;
  }
}

selection_sort.rs

/* 选择排序 */
fn selection_sort(nums: &mut [i32]) {
    if nums.is_empty() {
        return;
    }
    let n = nums.len();
    // 外循环：未排序区间为 [i, n-1]
    for i in 0..n - 1 {
        // 内循环：找到未排序区间内的最小元素
        let mut k = i;
        for j in i + 1..n {
            if nums[j] < nums[k] {
                k = j; // 记录最小元素的索引
            }
        }
        // 将该最小元素与未排序区间的首个元素交换
        nums.swap(i, k);
    }
}

selection_sort.c

/* 选择排序 */
void selectionSort(int nums[], int n) {
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

selection_sort.kt

/* 选择排序 */
fun selectionSort(nums: IntArray) {
    val n = nums.size
    // 外循环：未排序区间为 [i, n-1]
    for (i in 0..<n - 1) {
        var k = i
        // 内循环：找到未排序区间内的最小元素
        for (j in i + 1..<n) {
            if (nums[j] < nums[k])
                k = j // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        val temp = nums[i]
        nums[i] = nums[k]
        nums[k] = temp
    }
}

selection_sort.rb

[class]{}-[func]{selection_sort}

selection_sort.zig

[class]{}-[func]{selectionSort}

Code Visualization

Full Screen >

11.2.1   Algorithm characteristics

• Time complexity of \(O(n^2)\), non-adaptive sort: There are \(n - 1\) rounds in the outer loop, with the unsorted interval length starting at \(n\) in the first round and decreasing to \(2\) in the last round, i.e., the outer loops contain \(n\), \(n - 1\), \(\dots\), \(3\), \(2\) inner loops respectively, summing up to \(\frac{(n - 1)(n + 2)}{2}\).
• Space complexity of \(O(1)\), in-place sort: Uses constant extra space with pointers \(i\) and \(j\).
• Non-stable sort: As shown in Figure 11-3, an element nums[i] may be swapped to the right of an equal element, causing their relative order to change.

Figure 11-3   Selection sort instability example

Feel free to drop your insights, questions or suggestions