Grafische Erläuterung des Prinzips des Auswahlsortierungsalgorithmus und Implementierungsbeispiele in Python

Grundidee: Finden Sie das kleinste Element aus der unsortierten Sequenz und platzieren Sie es an der ersten Position, suchen Sie dann das kleinste Element aus der verbleibenden unsortierten Sequenz und platzieren Sie es an der zweiten Position usw. Und so weiter, bis alle Elemente sortiert sind. Unter der Annahme, dass es insgesamt n+1 Sequenzelemente gibt, müssen wir n Runden finden, um die Sequenz zu sortieren. In jeder Runde können wir Folgendes tun: Vergleichen Sie das erste Element der unsortierten Sequenz mit den nachfolgenden Elementen. Wenn die nachfolgenden Elemente kleiner sind, werden die nachfolgenden Elemente und das erste Element auf diese Weise vertauscht. Der erste muss der kleinste sein. Auf diese Weise können n Runden sortiert werden.

Schematische Darstellung
Abbildung 1:

Abbildung 2:

Die anfänglichen Daten sind nicht vertraulich. Unabhängig davon, ob die anfänglichen Daten sortiert sind oder nicht, müssen N2/2-Vergleiche durchgeführt werden. Dies gilt für einige Daten, die ursprünglich sortiert sind annähernd sortiert. Es gibt keinen Vorteil hinsichtlich der Reihenfolge. Im besten Fall, also wenn alles sortiert ist, sind 0 Austausche erforderlich, im schlechtesten Fall sind in umgekehrter Reihenfolge N-1 Austausche erforderlich.

Daten werden seltener ausgetauscht, wenn ein Element an der richtigen Endposition ist, wird es nicht verschoben. Im schlimmsten Fall sind nur N-1-Datenaustausche erforderlich. Unter allen Sortiermethoden, die zum Verschieben von Elementen ausschließlich auf Austauschen basieren, ist die Auswahlsortierung die bessere.

Python-Code-Implementierung:

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

Testen Sie es:

>>> 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]

Weitere Bilder und Texte, die das Prinzip des Auswahlsortierungsalgorithmus und Implementierungsbeispiele in Python erläutern, finden Sie auf der chinesischen PHP-Website für Verwandte Artikel!