选择排序 Python
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15235264/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Selection Sort Python
提问by lord12
This may seem like a simple question but when I attempted to implement selection sort in Python, I do not get a sorted list. Is there something wrong with my implementation? The subsetting may be a problem.
这似乎是一个简单的问题，但是当我尝试在 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
采纳答案by Ryan Morlok
I think there were a couple issues.
我认为有几个问题。
First, when your do source[i:], I believe that returns a new array of the sub-elements requested and not part of the original array, thus if you modify it, your don't modify the original. Second, you were subtracting 1 from an index when you shouldn't.
首先，当你做 source[i:] 时，我相信它会返回一个新的请求子元素数组，而不是原始数组的一部分，因此如果你修改它，你不会修改原始数组。其次，当您不应该从索引中减去 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
This gives:
这给出：
[1, 2, 3, 4, 5, 10, 100]
回答by steveha
Here is how I would rewrite your code. Of course in Python I would just use list.sort()to sort a list, but here is a selection sort in Python.
这是我将如何重写您的代码。当然，在 Python 中我只是list.sort()用来对列表进行排序，但这里是 Python 中的选择排序。
We make a generator expression that returns tuples of (value, i)for a value and its index from the list. Then when min()evaluates to find minimum, it finds the lowest tuple value; since the value comes first in the tuple before the index, the value will be the important part, and min()will find the lowest value. (If there is a tie, min()will use the second part of the tuple, the index, as a tie-breaker. But for sort we don't care how ties are broken.)
我们创建了一个生成器表达式，(value, i)它从列表中返回一个值及其索引的元组。然后当min()求得最小值时，它会找到最低的元组值；由于值在索引之前的元组中排在第一位，因此该值将是重要的部分，并且min()会找到最低的值。（如果有平局，min()将使用元组的第二部分，即索引，作为决胜局。但对于排序，我们不关心平局是如何被打破的。）
Now, instead of searching through the sub-list to find the min value, and then searching through it again to figure out the index, we search through it once and get both min value and index.
现在，我们不再搜索子列表以找到最小值，然后再次搜索以找出索引，而是搜索一次并获得最小值和索引。
But we don't actually care about the min value; we care about the index. So after min()is done, we just throw away the actual value but keep the index. Adjust the index to be correct in the whole list (not in the slice of the list) and then we can swap.
但我们实际上并不关心最小值；我们关心索引。所以min()完成后，我们只是扔掉实际值但保留索引。调整索引在整个列表中（不是在列表的切片中）正确，然后我们可以交换。
We use the standard Python idiom for swapping two values. Python will build a tuple object to be the intermediate, then unpack this tuple into the left-hand-side.
我们使用标准的 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)
EDIT: And here is a refinement of the above. A slice from a list actually allocates a new list; our code here doesn't need a new list, it just needs a convenient way to examine a sublist. The itertoolsmodule offers a function, islice(), that returns an iterator that iterates over a slice of a list. This avoids repeatedly creating and destroying lists as we examine each sublist.
编辑：这里是对上述内容的改进。列表中的切片实际上分配了一个新列表；我们这里的代码不需要新列表，它只需要一种方便的方法来检查子列表。该itertools模块提供了一个函数，islice()，它返回一个迭代器，该迭代器在列表的一个切片上进行迭代。这避免了在我们检查每个子列表时重复创建和销毁列表。
I believe this is the most efficient way to do selection sort in Python. (You could get rid of the part where we bind the generator expression to the name genexpand save a few microseconds... just make the call to min()a long one-liner. But it's not really worth the loss of readability.)
我相信这是在 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)
回答by user4795998
def Selection_Sort(Sarray):
length = len(Sarray)
i = 0
j = 0
for i in range(length):
j = i+1
for j in range(length):
if Sarray[i] < Sarray[j]
t = Sarray[i]
Sarray[i] = Sarray[j]
Sarray[j] = t
j = j+1
i = i+1
return Sarray
回答by David Yachnis
Code of select sort from MIT online course .
来自麻省理工学院在线课程的选择排序代码。
def selSort(L):
for i in range(len(L) - 1):
minIndx = i
minVal = L[i]
j = i+1
while j < len(L):
if minVal > L[j]:
minIndx = j
minVal = L[j]
j += 1
if minIndx != i:
temp = L[i]
L[i] = L[minIndx]
L[minIndx] = temp
回答by Yang Wang
def selectSort(L):
for i in range(len(L)):
print L
minIndex = i
minValue = L[i]
j = i + 1
while j < len(L):
if minValue > L[j]:
minIndex = j
minValue = L[j]
j +=1
temp = L[i]
L[i] = L[minIndex]
L[minIndex] = temp
回答by Vibhore Gupta
def ss(l):
for i in range(0,len(l)):
d=l.index(min(l[i:]))
c=l[i]
l[i]=min(l[i:])
l[d]=c
print(l) #it prints each step of selection sort
y=[10,9,1,5,0,6]
ss(y)
回答by urnatatio
here is what I think is a good way to sort a list of numbers and I hope it helps:
这是我认为对数字列表进行排序的好方法，我希望它有所帮助：
list=[5,4,3,1,6,8,10,9]
listsorted=[]
for i in range(len(list)):
x=min(list)
list.remove(x)
listsorted.append(x)
print listsorted
and the result will be [1, 3, 4, 5, 6, 8, 9, 10]
结果将是 [1, 3, 4, 5, 6, 8, 9, 10]
回答by Amjad
def selSort(L):
"""
Find the smallest element in the list and put it (swap it) in the first location,
Find the second element and put it (swap it) in the second locaiton, and so on.
"""
for i in range(len(L) - 1):
minIndx = i
minVal= L[i]
j = i + 1
while j < len(L):
if minVal > L[j]:
minIndx = j
minVal= L[j]
j += 1
temp = L[i]
L[i] = L[minIndx]
L[minIndx] = temp
return L
Call:
称呼：
print( selSort([120,11,0,1,3,2,3,4,5,6,7,8,9,10]) )
Output
输出
[0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 120]
回答by Himanshu Soni
s = [1,8,4,9,3,6,2]
for i in range(len(s)):
maxi = max(s[0:len(s)-i]) #find max element
tempi = s.index(maxi) # find index of max element
temp = s[len(s)-1-i] #assign last element as temp
s[len(s)-1-i] = maxi #put max element in last position
s[tempi] = temp # put the element initially at last in its new
print s
回答by billr
I think the "accepted" answer here is unhelpful. If we look at e.g.
我认为这里“接受”的答案是无益的。如果我们看例如
mini = min(source[i:]) #find minimum element
min_index = source[i:].index(mini) #find index of minimum element
not only is this inefficient in terms of creating list slices unnecessarily, but they are searched unnecessarily. It's reasonably concise but I don't think it's the best solution.
这不仅在不必要地创建列表切片方面效率低下，而且还被不必要地搜索。它相当简洁，但我认为这不是最好的解决方案。
