这看起来可能是一个简单的问题,但是当我尝试在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
发布于 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]
发布于 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)
发布于 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
复制相似问题