不预先找最小值、找到比当前元素更小就交换的排序算法属于什么类型？

你给出的这种排序实现属于简单交换排序（也叫直接交换排序），归属于交换排序大类，和标准选择排序、冒泡排序同属时间复杂度为O(n²)的基础比较排序算法。

和常见同复杂度排序的区别 #

• 和标准选择排序的差异：标准选择排序每轮外层遍历只会先记录最小值的下标，遍历完本轮所有元素后仅执行1次交换操作；你给出的实现每轮外层遍历遇到比基准元素小的值就立刻交换，每轮最多可执行n-i次交换，交换操作的开销远高于标准选择排序。
• 和标准冒泡排序的差异：标准冒泡排序的内层遍历仅比较相邻元素，通过多次相邻交换把极值「移动」到数组一端；你给出的实现是直接拿当前基准位置元素和后续所有非相邻元素比较，不符合冒泡排序的相邻交换特征。

该实现的核心特性 #

• 时间复杂度：最好、最坏、平均情况均为O(n²)，没有提前终止逻辑，即使输入数组已经完全有序，也会走完所有循环判断。
• 空间复杂度：O(1)，属于原地排序算法。
• 稳定性：不稳定排序，值相同的元素经过排序后相对位置可能发生变化。

对应实现代码 #

def sort(list):
    n = len(list)
    if n > 1:
        for i in range(n):
            for j in range(i+1, n):
                if list[i] > list[j]:
                    tmp = list[i]
                    list[i] = list[j]
                    list[j] = tmp
    return list

内容的提问来源于stack exchange，提问作者RaJan Kumar