选择排序（Selection）

发表于 2022-03-15 分类于 Algorithm Changyan：

选择排序

选择排序

排序算法	平均事件复杂度	最好情况	最坏情况	空间复杂度	稳定性	排序方式
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	In-place

简介

选择排序（Selection sort）是一种简单直观的排序算法。选择排序是不稳定的排序方法。

算法思想

排序原理步骤

遍历一遍找到最小数，记录下标
将该下标的数与第一个数交换，第一个数的位置确定
重复1，2步骤寻找第二个最小的数

选择排序

代码实现

for (int i = 0; i < a.length; i++) {
    int min = i;
    // 选择最小的数的下标
    for (int j = i+1; j < a.length; j++) {
        if(less(a[j], a[min])) min = j;
    }
    // 交换当前位置与最小的数
    exch(a, min, i);
}

算法分析

最好情况

最坏情况

空间复杂度

0%