在 Python 子列表中查找最小值的索引 - min() returns 列表中最小值的索引

Question

我一直致力于将常见的排序算法实现到 Python，而在研究 selection sort 时，我运行遇到了寻找子列表的最小值并交换它的问题子列表的第一个值，从我的测试来看，这似乎是由于我在程序中使用 min() 的方式存在问题。

这是我的代码：

def selection_sort(li):
    for i in range(0, len(li)):
        a, b = i, li.index(min(li[i:]))
        li[a], li[b] = li[b], li[a]

这适用于其中包含零个重复元素的列表：

>>> selection_sort([9,8,7,6,5,4,3,2,1])
[1, 2, 3, 4, 5, 6, 7, 8, 9]

但是，当列表中有重复元素时，它会完全失败。

>>> selection_sort([9,8,8,7,6,6,5,5,5,4,2,1,1])
[8, 8, 7, 6, 6, 5, 5, 5, 4, 2, 9, 1, 1]

我试图通过检查 min() 在我代码的第 3 行做了什么来解决这个问题，发现 min() returns 中最小元素的索引值子列表，但索引是更大列表中的元素而不是子列表，我希望这个实验有助于更清楚地说明：

>>> a = [1,2,1,1,2]
>>> min(a)
1                       # expected
>>> a.index(min(a))
0                       # also expected
>>> a.index(min(a[1:]))
0                       # should be 1?

我不确定是什么导致了这种行为；可以将 li[i:] 复制到一个临时变量 b 然后执行 b.index(min(b))，但是对于每个循环将 li[i:] 复制到 b 可能需要很多内存和选择排序是 in-place algorithm 所以我不确定这种方法是否理想。

Answer 1

一种方法是使用列表理解：

idxs = [i for i, val in enumerate(a) if val == min(a)]

或者更好的是，编写自己的代码，渐近速度更快：

idxs = []
minval = None
for i, val in enumerate(a):
    if minval is None or minval > val:
        idxs = [i]
        minval = val
    elif minval == val:
        idxs.append(i)

Answer 2

当您写 a.index(min(a[1:])) 时，您正在搜索 a[1:] 的 min 的第一次出现，但您在原始列表 中搜索 [=21] =].这就是为什么你会得到 0 作为结果。

顺便说一句，您要查找的函数通常称为argmin。它不包含在纯 python 中，但 numpy 模块中有它。

Answer 3

您没有完全理解正确的概念！

li.index(item) 将 return 该项目在列表 li 中的第一次出现。你应该做的是，如果你在子列表中找到最小元素，那么也在子列表中搜索该元素，而不是在整个列表中搜索它。此外，在切片列表中搜索时，您将获得关于子列表的索引。尽管您可以通过将起始步骤添加到索引 returned.

来轻松解决此问题

针对您的问题的一个小修复是：

def selection_sort(li):
    for i in range(0, len(li)):
        a, b = i, i + li[i:].index(min(li[i:]))
        li[a], li[b] = li[b], li[a]

在 Python 子列表中查找最小值的索引 - min() returns 列表中最小值的索引

Find index of minimum value in a Python sublist - min() returns index of minimum value in list

python

sorting

min

sublist