为什么这个算法可以按降序对数据进行排序

Question

我学习python编程并尝试按降序对数据进行排序。下面的#sort1 已成功排序，但我不明白为什么会发生这种情况。还有，data[i], data[data.index(mn)] = data[data.index(mn)], data[I]就是疑点。data = [-1.48,  4.96,  7.84, -4.27,  0.83,  0.31, -0.18,  3.57,  1.48,  5.34,         9.12,  7.98, -0.75,  2.22, -1.16,  6.53, -5.38,  1.63, -2.85,  7.89,        -5.96, -8.23,  8.76, -2.97,  4.57,  5.21,  9.43,  3.12,  6.52,  1.58 ]#sort1for i in range(30):    mn = data[i]    for j in data:        if j < mn:            mn = j            data[i], data[data.index(mn)] = data[data.index(mn)], data[i]        else:            passprint('ascending order1:')print(data)

Answer 1

这是插入排序https://en.wikipedia.org/wiki/Insertion_sort

您可以将其想象为对项目的流式列表进行排序：

for i in range(30): # for each item streamed here

    mn = data[i]    # take the new item (if exists new item)

    for j in data:  # find its place in the sorted data, and insert it there:

        if j < mn:  # if found its place, insert it here

            mn = j  

            data[i], data[data.index(mn)] = data[data.index(mn)], data[i] 

更新

插入排序背后的直觉是，每次获得新项目时，您都会更新先前排序的列表。因此，您无需担心未来项目的排序位置。

由于时间之前的数据i是排序的，那么在找到第一个交换之后，所有的项目都会交换，直到它再次到达时间i。

现在，交换命令的问题：

data[i], data[data.index(mn)] = data[data.index(mn)], data[i] 

实际上，这个交换命令会忽略未来的交换（何时data.index(mn)大于当前时间i）。但是，由于它在时间i大于时起作用data.index(mn)，因此对于插入排序来说已经足够了。这是一个例子：

# two attempts to swapping x and y: 

data = ['x', 'y']

# ignored (target of swap is at time i, found position in future!):

i = 0; mn = 'y' # data.index(mn) == 1

data[i], data[data.index(mn)] = data[data.index(mn)], data[i] 

print('ignored swap', data) 

# success (target of swap is at time i, found position in past (before i)):

i = 1; mn = 'x' # data.index(mn) == 0

data[i], data[data.index(mn)] = data[data.index(mn)], data[i] 

print('success swap', data)

Answer 2

您的代码中有 2 个错误：

最好在循环中执行for i in range(len(data))，因此如果变量数据的大小发生变化，您的代码将起作用。

您的代码按降序对数据进行排序，因此您应该打印：print('descending order1:')

现在，让我们谈谈算法部分。实际上，您的代码是排序算法冒泡排序的实现，也称为下沉排序。该算法重复遍历列表并比较相邻元素。如果它们的顺序错误（即如果第一个元素低于第二个），它将交换相邻元素。它这样做直到列表被排序（按降序排列）。你可以在这里得到更多的了解

代码data[i], data[data.index(mn)] = data[data.index(mn)], data[i]只是交换部分。这是一种交换元素的 Pythonic 方式。例如：

a = 5

b = 15

a, b = b, a # swap 'elegantly a and b

print(a) #  display 15

print(b) # display 5

代码评论：

for i in range(30): # first cursor: steps through the indexes of the list

    mn = data[i]    # assigns the data at index i to the variable mn

    for j in data:  # second cursor: steps through the data of the list

        if j < mn:  # compares adjacent elements

            mn = j  

            data[i], data[data.index(mn)] = data[data.index(mn)], data[i] # swap adjacent elements

        else: # if the first data superior to the second, don't do anything

            pass