Explication graphique du principe de l'algorithme de tri par sélection et exemples d'implémentation en Python

Idée de base : Trouvez le plus petit élément de la séquence non triée et mettez-le en première position, puis trouvez le plus petit élément de la séquence non triée restante et mettez-le en deuxième position, etc. Et ainsi jusqu'à ce que tous les éléments aient été triés. En supposant qu’il y a n 1 éléments de séquence au total, nous devons trouver n tours pour trier la séquence. À chaque tour, nous pouvons faire ceci : comparer le premier élément de la séquence non triée avec les éléments suivants en séquence. Si les éléments suivants sont plus petits, les éléments suivants et le premier élément seront échangés de cette façon, après un tour. Le premier doit être le plus petit. De cette façon, n tours peuvent être triés.

Diagramme schématique
Figure 1 :

Figure 2 :

Les données initiales ne sont pas sensibles. Peu importe que les données initiales soient triées ou non, elles doivent passer par des comparaisons N2/2. Ceci concerne certaines données initialement triées ou non. approximativement triés. Il n'y a aucun avantage en termes de séquence. Dans le meilleur des cas, c'est-à-dire que tout est trié, 0 échange est nécessaire, et dans le pire des cas, dans l'ordre inverse, N-1 échanges sont nécessaires.

Les données sont échangées moins souvent, si un élément est dans la bonne position finale, il ne sera pas déplacé. Dans le pire des cas, seuls N-1 échanges de données sont nécessaires. Parmi toutes les méthodes de tri qui reposent entièrement sur les échanges pour déplacer des éléments, le tri par sélection est la meilleure.

Implémentation du code Python :

def sort_choice(numbers, max_to_min=True):
 """
 我这没有按照标准的选择排序，假设列表长度为n，思路如下：
  1、获取最大值x，将x移动到列最后。[n1, n2, n3, ... nn]
  2、将x追加到排序结果[n1, n3, ... nn, n2]
  3、获取排序后n-1个元素[n1, n3, ... nn]，重复第一步，重复n-1次。

 max_to_min是指从大到小排序，默认为true；否则从小到大排序。
 对[8, 4, 1, 0, 9]排序，大致流程如下：
 sorted_numbers = []
 [8, 4, 1, 0, 9], sorted_numbers = [9]
 [4, 1, 0, 8], sorted_numbers = [9, 8]
 [1, 0, 4], sorted_numbers = [9, 8, 4]
 [0, 1], sorted_numbers = [9, 8, 4, 1]
 [0], sorted_numbers = [9, 8, 4, 1, 0]
 """
 if len(numbers) <= 1:
  return numbers
 sorted_list = []
 index = 0
 for i in xrange(len(numbers) - index):
  left_numbers = _get_left_numbers(numbers, max_to_min)
  numbers = left_numbers[:-1]
  sorted_list.append(left_numbers[-1])
  index += 1
 return sorted_list

def _get_left_numbers(numbers, get_max=True):
 &#39;&#39;&#39;
 获取最大值或者最小值x，并且将x抽取出来，置于列表最后.
 Ex: get_max=True, [1, 4, 3] ⇒ [1, 3, 4] 
  get_max=False, [1, 4, 3] ⇒ [4, 3 ,1] 
 &#39;&#39;&#39;
 max_index = 0
 for i, num in enumerate(numbers):
  if get_max:
   if num > numbers[max_index]:
    max_index = i
  else:
   if num < numbers[max_index]:
    max_index = i
 numbers = numbers[:max_index] + numbers[max_index + 1:] + [numbers[max_index]]
 return numbers

Testez-le :

>>> get_left_numbers([0, 4, 0, 31, 9, 19, 89,67], get_max=True)
[0, 4, 0, 31, 9, 19, 67, 89]
>>> get_left_numbers([0, 4, 0, 31, 9, 19, 89,67], get_max=False)
[4, 0, 31, 9, 19, 89, 67, 0]

>>> sort_choice([0, 4, 0, 31, 9, 19, 89,67], max_to_min=False)
[0, 0, 4, 9, 19, 31, 67, 89]
>>> sort_choice([0, 4, 0, 31, 9, 19, 89,67], max_to_min=True)
[89, 67, 31, 19, 9, 4, 0, 0]

Pour plus d'images et de textes expliquant le principe de l'algorithme de tri par sélection et des exemples d'implémentation en Python, veuillez faire attention au site Web PHP chinois pour articles connexes!