python - 从 Python 开始 - 练习 8.14 排序算法。这个已经有名字了吗？

Question

所以，我正在阅读《从 Python 开始》这本书。我到了一个地步，没有教我任何排序算法，一个练习要求我按以下方式对包含日期和价格的文本文件进行排序。

年年月日:价格

即

04-05-1993:1.068
04-12-1993:1.079
04-19-1993:1.079
04-26-1993:1.086
05-03-1993:1.086

在我的沮丧中，我创建了两个列表。一个包含日期，一个包含价格。

然后我继续使用我想出的以下函数算法对它们进行排序。

我正在从列表中找到最低价格的索引，我将价格添加到 min_to_max_prices_algorithms。

def sort_algorithm(dates,prices):

     # Create two lists for storing the results.
     min_to_max_prices = []
     min_to_max_dates = []

     # List I will use to change the prices from str to float.
     price_list = []

     # Set the date_list to dates
     date_list = dates

     # Change the prices to float numbers.
     for index in range(len(prices)):
         price_list.append(float(prices[index]))

     # Algorithm
     for count in range(len(price_list)):

         # Find the minimum price and append it to min_to_max_prices list.
         min_to_max_prices.append(min(price_list))

         # Use the index of the minimum price to add the equivalent
         # date to min_to_max_dates list.                                                 
         min_to_max_dates.append(dates[price_list.index(min(price_list))])

         # Remove the ones added from the lists we search in.
         del date_list[price_list.index(min(price_list))]
         del price_list[price_list.index(min(price_list))]

这种算法有名字吗？什么是更好的解决方案？很抱歉，我无法在任何地方找到问题的答案。

Answer 1

这看起来像 Selection Sort ，除非您为结果使用不同的列表，而该算法会就地对列表进行排序(即不需要临时列表)。该算法的工作原理如下:

def selection_sort(lst):
    for i in range(len(lst) - 1):
        for j in range(i + 1, len(lst)):
            if lst[i] > lst[j]:
                lst[i], lst[j] = lst[j], lst[i]

因此，基本上，外循环的每次迭代都会在剩余的未排序元素中找到最小元素。

选择排序很简单，但不是一个好的排序算法，因为它的时间复杂度是O(n^2)。 , 虽然你可以做得和 O(nlogn) 一样好(see some examples on wikipedia)。