选择排序 Selection sort

选择排序的逻辑很简单, 将数组分成两部分:

左侧部分是排序好的, 按顺序放着较小的元素
右侧部分是未排序的, 放着较大的元素

选择排序的步骤

遍历数组, 找到最小的元素, 让它与最左侧元素交换
遍历数组中剩下的元素, 找到最小的元素, 让它与最左侧第二位元素交换
重复上面的步骤, 直到所有元素都有序排列

我们以 arr = [9, 4, 1, 7]; 为例进行演示:

首先找到最小的元素 1, 把它与最左侧元素相交换:

selection sort pass 1

第二阶段, 找到剩下元素中最小的元素 4, 把它与左侧第二位相交换:

selection sort pass 2

第三阶段, 找到最小的元素 7, 把它与左侧第三个元素相交换:

selection sort pass 3

到达了数组的最右侧, 所有元素都已排好序.

选择排序的代码实现

#![allow(unused)]
fn main() {
pub fn selection_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    if arr.len() < 2 {
        return;
    }
    for i in 0..(len - 1) {

        // 找到最小元素的索引
        let mut min_index = i;
        for j in (i + 1)..len {
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }

        // 如果最小元素不是 `list[i]`, 就交换两个元素
        if i != min_index {
            arr.swap(i, min_index);
        }
    }
}
}

递归实现选择排序

以上代码是用的迭代方式实现的选择排序, 接下来我们以递归的方式重新实现它.

#![allow(unused)]
fn main() {
/// 递归实现选择排序
pub fn recursive_selection_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    fn get_min_index<T>(list: &[T], i: usize, len: usize) -> usize
    where
        T: PartialOrd,
    {
        if i == len - 1 {
            return i;
        }
        let j = get_min_index(list, i + 1, len);
        if list[i] < list[j] {
            i
        } else {
            j
        }
    }

    let len = arr.len();
    if arr.len() < 2 {
        return;
    }

    let min_index = get_min_index(arr, 0, len);
    // 将最小的元素交换到最左侧
    if min_index != 0 {
        arr.swap(0, min_index);
    }

    // 递归排序剩下的元素
    recursive_selection_sort(&mut arr[1..]);
}
}

优化选择排序

默认实现的选择排序, 在每次循环时会找到最小的元素, 然后把它放在数组的左侧部分. 每次循环时, 我们可以同时找到最大的元素, 然后把它放在数组的右侧部分. 这样的话, 每个循环就可以同时找到最小和最大的元素.

#![allow(unused)]
fn main() {
/// 选择排序的一个小优化.
///
/// 将最小的元素放在左侧的同时, 将最大的元素放在右侧.
pub fn two_way_selection_sort<T>(arr: &mut [T])
where
    T: PartialOrd + std::fmt::Debug,
{
    let len = arr.len();
    if arr.len() < 2 {
        return;
    }

    let mut start = 0;
    let mut end = len - 1;
    while start < end {
        // 找到最小元素的索引
        let mut min_index = start;
        let mut max_index = start;
        for i in start..=end {
            if arr[i] < arr[min_index] {
                min_index = i;
            }
            if arr[i] > arr[max_index] {
                max_index = i;
            }
        }

        // 交换最小元素
        if start != min_index {
            arr.swap(start, min_index);
        }

        // 交换最大元素
        if end != max_index {
            if start == min_index {
                // 如果没有交换最小元素, 说明数组中的元素还没有移动过, 可以直接交换
                arr.swap(end, max_index);
            } else {
                // 这时, 最小元素已经移到了最左侧, 我们需要判断这个移位操作给最大值带来的影响.
                if max_index == start {
                    // 此时, 最大值已经被移到了 `list[min_index]`.
                    if end != min_index {
                        arr.swap(end, min_index);
                    }
                } else {
                    arr.swap(end, max_index);
                }
            }
        }

        start += 1;
        if end > 1 {
            end -= 1;
        }
    }
}
}

选择排序支持稳定排序

默认实现的选择排序算法, 是将最小元素交换到它的目标位置, 这样的话移动元素的次数很少, 但是是不稳定排序. 为了实现稳定排序, 我们可以插入排序的方式, 将最小元素插入到目标位置, 然后将其它元素向右移动一个位置, 尽管这样一来性能比较差.

#![allow(unused)]
fn main() {
/// 选择排序的一个小优化.
///
/// 将最小的元素放在左侧的同时, 将最大的元素放在右侧.
pub fn two_way_selection_sort<T>(arr: &mut [T])
where
    T: PartialOrd + std::fmt::Debug,
{
    let len = arr.len();
    if arr.len() < 2 {
        return;
    }

    let mut start = 0;
    let mut end = len - 1;
    while start < end {
        // 找到最小元素的索引
        let mut min_index = start;
        let mut max_index = start;
        for i in start..=end {
            if arr[i] < arr[min_index] {
                min_index = i;
            }
            if arr[i] > arr[max_index] {
                max_index = i;
            }
        }

        // 交换最小元素
        if start != min_index {
            arr.swap(start, min_index);
        }

        // 交换最大元素
        if end != max_index {
            if start == min_index {
                // 如果没有交换最小元素, 说明数组中的元素还没有移动过, 可以直接交换
                arr.swap(end, max_index);
            } else {
                // 这时, 最小元素已经移到了最左侧, 我们需要判断这个移位操作给最大值带来的影响.
                if max_index == start {
                    // 此时, 最大值已经被移到了 `list[min_index]`.
                    if end != min_index {
                        arr.swap(end, min_index);
                    }
                } else {
                    arr.swap(end, max_index);
                }
            }
        }

        start += 1;
        if end > 1 {
            end -= 1;
        }
    }
}
}

选择排序的特点

即使数组中的元素基本排序好, 也需要遍历所有元素并比较大小, 这种情况下效率较低, 依然需要 n^2 / 2 次比较操作以及 n 次交换, 平均时间复杂度是 O(n log(n)), 空间复杂度是 O(1)
在所有排序算法中, 选择排序移动元素的次数最少, 每个元素最多只移动一次, 就可以移到最终位置; 这个算法比较适合那种比较元素时的成本低, 但移动元素成本比较高的情况 (比如, 移动文件中的内容)
选择排序是原地排序 (in-place sort)
选择排序是 in-adaptive sort
默认实现的选择排序算法是不稳定排序 (unstable), 但优化后的算法可以实现稳定排序 (stable sort)

数据结构与算法 - Rust 语言实现