选择排序Python
这看起来可能是一个简单的问题，但是当我尝试在Python中实现选择排序时，我没有得到一个排序列表。我的实现有什么问题吗？子设置可能是一个问题。
source = [4,2,1,10,5,3,100]
for i in range(len(source)):
mini = min(source[i:]) #find minimum element
min_index = source[i:].index(mini)-1 #find index of minimum element
source[i:][min_index]= source[i:][0] #replace element at min_index with first element
source[i:][0] = mini #replace first element with min element
print source回答 13
Stack Overflow用户
发布于 2013-03-06 06:30:00
我想有几个问题。
首先，当你做sourcei:时，我相信会返回一个新的请求的子元素数组，而不是原始数组的一部分，因此如果你修改了它，你就不会修改原始数组。第二，你从索引中减去了1，而你不应该这样做。
source = [4,2,1,10,5,3,100]
for i in range(len(source)):
mini = min(source[i:]) #find minimum element
min_index = source[i:].index(mini) #find index of minimum element
source[i + min_index] = source[i] #replace element at min_index with first element
source[i] = mini #replace first element with min element
print source这提供了：
[1, 2, 3, 4, 5, 10, 100]Stack Overflow用户
发布于 2013-03-06 07:01:20
下面是我如何重写你的代码。当然，在Python语言中，我只会使用list.sort()对列表进行排序，但在Python语言中，这是一种选择排序。
我们创建了一个生成器表达式，它返回值的(value, i)元组及其列表中的索引。然后，当min()求值为查找minimum时，它将查找最低的元组值；由于该值在元组中排在索引之前，因此该值将是最重要的部分，而min()将查找最低的值。(如果存在平局，min()将使用元组的第二部分，即索引，作为平局的决定者。但对于排序，我们并不关心关系是如何被打破的。)
现在，我们不再搜索子列表来查找最小值，然后再次搜索它来确定索引，而是搜索一次，得到最小值和索引。
但我们实际上并不关心最小值；我们关心的是索引。因此，在min()完成后，我们只需丢弃实际值，但保留索引。将索引调整为在整个列表中正确(而不是在列表的片段中)，然后我们就可以交换了。
我们使用标准的Python惯用法来交换两个值。Python将构建一个元组对象作为中间层，然后将该元组解压到左侧。
lst = [4,2,1,10,5,3,100]
for i_sortpos in range(len(lst)):
# Make a generator expression to return (value, i) pairs.
genexp = ((n, i) for i, n in enumerate(lst[i_sortpos:]))
# Use genexp with min() to find lowest and its index.
# (Use '_' for variable name for the actual value; we don't use it.)
_, i_min = min(genexp)
# Adjust index to be correct in full list.
i_min += i_sortpos
# Swap the number at i_sortpos with the lowest found.
lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos]
print(lst)编辑:这是对上面内容的改进。列表中的片段实际上分配了一个新的列表；我们的代码不需要新的列表，它只需要一种方便的方法来检查子列表。itertools模块提供了一个函数islice()，该函数返回迭代列表片段的迭代器。这避免了在我们检查每个子列表时重复创建和销毁列表。
我相信这是在Python中进行选择排序的最有效的方法。(您可以去掉将生成器表达式绑定到名称genexp的部分，并节省几微秒的时间……只需让对min()的调用成为一个很长的一行代码。但失去可读性是不值得的。)
import itertools as it
lst = [4,2,1,10,5,3,100]
for i_sortpos in range(len(lst)):
# Make a generator expression to return (value, i) pairs.
# Use it.islice() for to look at sublist.
genexp = ((n, i) for i, n in enumerate(it.islice(lst, i_sortpos, len(lst))))
# Use genexp with min() to find lowest and its index.
# (Use '_' for variable name for the actual value; we don't use it.)
_, i_min = min(genexp)
# Adjust index to be correct in full list.
i_min += i_sortpos
# Swap the number at i_sortpos with the lowest found.
lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos]
print(lst)Stack Overflow用户
发布于 2017-11-01 17:54:08
def selectionSort(List_):
for i in range(len(List_)):`
#track the current smallest value
smallIndex = i
#loop from the current smallest value
for j in range(i+1,len(List_))
if List_[j] < List_[smallIndex]:
#if new value is less that our smallest value,change
#smallest value to this
smallIndex = j
if smallIndex != i:
#swap the values
List_[smallIndex],List_[i] = List_[i],List_[smallIndex]
#return sorted list
return List_https://stackoverflow.com/questions/15235264
复制相似问题
腾讯云开发者
