追加到新数组后从数组中删除最小值

Question

我在 Python 中运行一个选择排序函数，它适用于 numpy 数组而不是列表(所以我不能为此使用 .pop，我不认为(。

函数为：

def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr) 
newArr.append((smallest)) 
arr = arr[(arr > smallest)]
return newArr

我希望"arr = arr[(arr> smallest(]显然不起作用，以与 .pop 对列表相同的方式从传递的数组中删除最小值(或附加到 newArr 的值，即相同的值(。

我已经尝试了以下方法：

a = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9])
index = [2, 3, 6]
new_a = np.delete(a, index)

但无法让它工作。归根结底，我需要以以下格式获取一些东西：

arr = randint(0,10,20)

返回按升序排序的数组。我所能管理的就是返回重复的最小值。

感谢您的任何帮助

Answer 1

试试

arr = arr[np.where(arr > smallest)]

Answer 2

你可以试试：

arr = arr[ arr != np.min(a)]

这样，您将从arr除最小元素之外的所有元素中获取并将它们重新分配给arr。

Answer 3

你的算法几乎是正确的。事实上，如果arr中没有重复的值，它就可以工作：

import numpy as np
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr) 
newArr.append((smallest)) 
arr = arr[(arr > smallest)]
return newArr
findSmallest = np.min
# no duplicate values
auniq = np.random.choice(np.arange(20), (10,), replace=False)
print(auniq)
print(selectionSort(auniq))

示例运行：

[ 0  1  7  4 10 14 13 16  9 12]
[0, 1, 4, 7, 9, 10, 12, 13, 14, 16]

如果有重复项，它将崩溃，因为在删除具有重复项的最小值时，重复项也将被删除，这会抛弃循环的逻辑。

# duplicate values
adupl = np.random.randint(0, 9, (10,))
print(adupl)
# next line would crash
#print(selectionSort(adupl))

一种解决方法是仅删除重复项的一个副本。例如，这可以使用返回/一个最小值的索引而不是其值的argmin来完成。

def selectionSort2(arr):
arr = np.array(arr)
sorted = np.empty_like(arr)
for i in range(len(sorted)):
j = arr.argmin()
sorted[i] = arr[j]
arr = np.delete(arr, j)
return sorted
print(selectionSort2(adupl))

这有效，但效率非常低np.delete因为或多或少是O(n(。将最小元素与边界元素交换，然后将其切断会更便宜：

def selectionSort3(arr):
arr = np.array(arr)
sorted = np.empty_like(arr)
for i in range(len(sorted)):
j = arr[i:].argmin()
sorted[i] = arr[i + j]
arr[i], arr[i + j] = arr[i + j], arr[i]
return sorted
print(selectionSort3(adupl))

查看selectionSort3我们可以观察到实际上并不需要单独的输出sorted，因为arr已经就地排序了：

def selectionSort4(arr):
arr = np.array(arr)
for i in range(len(arr)):
j = arr[i:].argmin()
arr[i], arr[i + j] = arr[i + j], arr[i]
return arr
print(selectionSort4(adupl))

样本输出(adupl和selectionSort2-4输出(：

[0 4 3 8 8 4 5 0 4 2]
[0 0 2 3 4 4 4 5 8 8]
[0 0 2 3 4 4 4 5 8 8]
[0 0 2 3 4 4 4 5 8 8]