Heim  >  Artikel  >  Backend-Entwicklung  >  Python-Schnellsortierung, Einfügungssortierungsalgorithmus, detaillierte Erläuterung benutzerdefinierter Sortierbeispiele

Python-Schnellsortierung, Einfügungssortierungsalgorithmus, detaillierte Erläuterung benutzerdefinierter Sortierbeispiele

伊谢尔伦
伊谢尔伦Original
2017-06-28 13:54:531822Durchsuche

Dieser Artikel stellt hauptsächlich Python vor, um schnelle Sortier- und Einfügungssortierungsalgorithmen zu implementieren und Beispiele für benutzerdefinierte Sortierung zu verwenden. Freunde in Not können sich darauf beziehen

1. Schnellsortierung

Quicksort ist eine Verbesserung der

Blasensortierung

. Vorgeschlagen von C. A. R. Hoare im Jahr 1962. Seine Grundidee besteht darin, die zu sortierenden Daten durch eine Sortierung in zwei unabhängige Teile aufzuteilen. Alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil und diese Methode wird dann verwendet, um die beiden Teile der Daten schnell zu trennen . Sortieren: Der gesamte Sortiervorgang kann rekursiv durchgeführt werden, sodass die gesamten Daten zu einer geordneten Sequenz werden. Schnelle Sortierung, rekursive Implementierung

def quick_sort(num_list):
  """
  快速排序
  """
  if num_list == []:
    return num_list
  smallList = []
  bigList = []
  middleElement = num_list[0]
  for i in num_list[1:]:
    if i <= middleElement:
      smallList.append(i)
    else:
      bigList.append(i)
  return quick_sort(smallList)+[middleElement]+quick_sort(bigList)
2. Einfügungssortierung

Die Algorithmusbeschreibung von Einfügungssortierung ist ein einfacher und intuitiver Sortieralgorithmus . Es funktioniert, indem es eine geordnete Sequenz erstellt. Bei unsortierten Daten scannt es die sortierte Sequenz von hinten nach vorne, findet die entsprechende Position und fügt sie ein. Bei der Implementierung der Einfügungssortierung wird normalerweise die In-Place-Sortierung verwendet (d. h. eine Sortierung, die nur O(1) zusätzlichen Platz beansprucht). Daher müssen die sortierten Elemente während des Scanvorgangs von hinten nach vorne wiederholt und schrittweise sortiert werden nach hinten verschoben, um Platz zum Einfügen des neuesten Elements zu schaffen.

Einfügungssortierung

def insert_sort(num_list):
  """
  插入排序
  """
  for i in range(len(num_list)-1):
    for j in range(i+1, len(num_list)):
      if num_list[i]>num_list[j]:
        num_list[i],num_list[j] = num_list[j],num_list[i]
  return num_list
3. Eine benutzerdefinierte Sortierung

kann durch Verwendung der Schlüssel sort() oder sorted() erreicht werden.
Beispiele sind wie folgt:

# Verwenden Sie die
def sort_key(obj):
  sorted_list = [4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
  return sorted_list.index(obj)
 
 
if name == &#39;main&#39;:
  print sorted(range(10), key=sort_key)
 
# 输出结果如下
[4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
Indexposition

des Schlüsselworts in der Liste, um eine benutzerdefinierte Sortierung durchzuführen

Das obige ist der detaillierte Inhalt vonPython-Schnellsortierung, Einfügungssortierungsalgorithmus, detaillierte Erläuterung benutzerdefinierter Sortierbeispiele. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn