Python 中的选择排序未排序

Question

我编写了一个选择排序程序，首先创建了一个函数来查找数组中的最小元素。然后我遍历数组，将最小的元素放在数组中的正确位置，同时替换最小的元素。这是我的代码：

a=[int(input()) for _ in range(6)]
def smallest_element(arr,x):
    smallest = arr[x]
    d = x
    for j in range(x+1,len(arr)):
        if arr[j] < smallest:
            smallest = arr[j]
            d = j
    return d
for i in range(0,len(a)):
    c = a[i]
    if(c > a[smallest_element(a,i)]):
        a[i] = a[smallest_element(a,i)]
        a[smallest_element(a,i)] = c
print(a)

但问题是我的数组没有排序。
输入 - [5,2,4,6,1,3]
输出 - [5,2,4,6,1,3]

Answer 1

错误似乎在你的循环中。

您将找到的最小值分配给当前索引。

a[i] = a[smallest_element(a,i)]

然后你将原来存储的值赋给最小元素所在的索引。

a[smallest_element(a,i)] = c

然而，您确实重新计算了最小元素的索引，它始终是当前索引 - 因为您只是将最小值复制到当前索引。

第一种方法

我知道这个问题有两种解决方案。首先，您只能在每个循环中搜索一次最小元素的索引。这样你就不会重新计算索引并写入正确的位置。

for i in range(0, len(a)):
    c = a[i]
    indexOfSmallestElement = smallest_element(a, i)
    smallestElement = a[indexOfSmallestElement]

    if c > smallestElement:
        a[i] = smallestElement
        a[indexOfSmallestElement] = c

第二种方法

另一种解决方案是从当前索引 + 1 而不是当前索引开始搜索元素，从而跳过您已经更改的条目。

交换 a[smallest_element(a, i)] = c 与 a[smallest_element(a, i + 1)] = c。

但是我建议使用第一种方法，因为它减少了数组迭代的次数。

Answer 2

首先，在您的代码中，您调用了 smallest_element(arr,x) 3 次，这将消耗更多时间用于更大的数组。相反，我们可以将该值存储到一个变量中，而不是调用 3 次。

其次，您交换了 2 次 一次在函数体 和 在 if 块 .

中

所以在函数体中，找到当前最小的元素。然后 return 到 main.Then 的索引如果它小于当前元素（在主 for 循环中），则交换它。

#Find the smallest element
def smallest_element(arr,x):
    small = x
    for j in range(x+1,len(arr)):
        if arr[j] < arr[small]:
            small=j
    return small

#now compare  it with the current element  
for i in range(0,len(a)):
    c = a[i]
    curr=smallest_element(a,i)

    if(c > a[curr] and curr!=i):
        a[i] = a[curr]
        a[curr] = c


    print(a)

Python 中的选择排序未排序

Selection Sort in Python not sorting

python-3.x

sorting

selection-sort

第一种方法

第二种方法