Detaillierte Einführung in die Implementierungsschritte des Merge-Sort-Algorithmus in der Python-Programmierung

Grundidee: Die Zusammenführungssortierung ist eine typische Divide-and-Conquer-Idee, die eine ungeordnete Liste in zwei Teile teilt, dann jede Teilsequenz erneut in zwei Teile teilt und so lange fortfährt, bis sie nicht mehr geteilt werden kann. Dann beginnt der Zusammenführungsprozess, bei dem die Elemente jeder Teilsequenz mit einer anderen Teilsequenz verglichen werden, die kleinen Elemente nacheinander zur Zusammenführung in die Ergebnissequenz eingefügt werden und schließlich die Zusammenführungssortierung abgeschlossen wird.

Zusammenführungsprozess:

Wenden Sie Platz an, sodass seine Größe der Summe der beiden sortierten Sequenzen entspricht. Dieser Platz wird zum Speichern der zusammengeführten Sequenz verwendet
Setzen Sie zwei Zeiger, die Anfangspositionen sind die Anfangspositionen der beiden sortierten Sequenzen.
Vergleichen Sie die Elemente, auf die die beiden Zeiger zeigen, wählen Sie das relativ kleine Element aus, legen Sie es in den Zusammenführungsbereich und bewegen Sie den Zeiger dorthin die nächste Position
Wiederholen Sie Schritt 3, bis ein bestimmter Zeiger das Ende der Sequenz erreicht
Kopieren Sie alle verbleibenden Elemente der anderen Sequenz direkt an das Ende der zusammengeführten Sequenz
Die obige Aussage ist eine theoretische Aussage. Hier ein praktisches Beispiel zur Veranschaulichung:

Zum Beispiel ein ungeordnetes Array

[6,2,3,1,7]

Zerlegen Sie das Array zunächst rekursiv bis:

[6],[2],[3],[1],[7]

Dann starten Sie die Zusammenführungssortierung, ebenfalls auf rekursive Weise:

Zusammenführen und zwei nach zwei sortieren, erhalten Sie:

[2,6],[1,3],[7]

Im vorherigen Schritt wurde es tatsächlich auf die gleiche Weise wie in diesem Schritt zusammengeführt, aber da jede Liste eine Nummer enthält, kann der Vorgang nicht vollständig angezeigt werden . Der Prozess kann unten vollständig dargestellt werden.

Anfänglich:

 a = [2,6] b = [1,3] c = []

Schritt 1, nehmen Sie nacheinander eine Zahl aus a, b heraus: 2, 1, vergleichen Sie die Größe und Geben Sie c ein und löschen Sie die Nummer aus der ursprünglichen Liste. Das Ergebnis ist:

a = [2,6] b = [3] c = [1]

Schritt 2, fahren Sie mit a, b fort Zahl, das heißt, wiederholen Sie die obigen Schritte, dieses Mal ist es: 2,3. Geben Sie sie in c ein und löschen Sie die Zahl aus der ursprünglichen Liste. Das Ergebnis ist:

a = [6] b = [3] c = [1,2]

Schritt 3, wiederholen Sie die vorherigen Schritte, das Ergebnis ist:

a = [6] b = [] c = [1,2,3]

Der letzte Schritt ist hänge 6 an c an, das Ergebnis ist:

a = [] b = [] c = [1,2,3,6]

Durch wiederholtes Anwenden des obigen Prozesses wird die Zusammenführung von [1,2,3,6] und [7] ist erreicht

Endlich das Sortierergebnis erhalten

[1,2,3,6,7]

In diesem Artikel werden drei Python-Implementierungsmethoden aufgeführt:

Methode 1: Übersetzen Sie den oben beschriebenen Prozess, etwas ungeschickt

#! /usr/bin/env python
#coding:utf-8

def merge_sort(seq):
 if len(seq) ==1:
 return seq
 else:
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])

 i = 0 #left 计数
 j = 0 #right 计数
 k = 0 #总计数

 while i < len(left) and j < len(right):
  if left[i] < right [j]:
  seq[k] = left[i]
  i +=1
  k +=1
  else:
  seq[k] = right[j]
  j +=1
  k +=1

 remain = left if i<j else right
 r = i if remain ==left else j

 while r<len(remain):
  seq[k] = remain[r]
  r +=1
  k +=1

 return seq

Methode 2: In Bezug auf das Nehmen von Werten in der Reihenfolge anwenden Ohne die list.pop()-Methode ist der Code kompakter und prägnanter

#! /usr/bin/env python
#coding:utf-8


def merge_sort(lst): #此方法来自维基百科

 if len(lst) <= 1:
 return lst

 def merge(left, right):
 merged = []

 while left and right:
  merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))

 while left:
  merged.append(left.pop(0))

 while right:
  merged.append(right.pop(0))

 return merged

 middle = int(len(lst) / 2) 
 left = merge_sort(lst[:middle])
 right = merge_sort(lst[middle:])
 return merge(left, right)

Methode 3: Es stellt sich heraus Diese Zusammenführung ist im Python-Modul heapq vorgesehen. Für die Sortiermethode importieren Sie einfach die zerlegten Ergebnisse in diese Methode.

#! /usr/bin/env python
#coding:utf-8


from heapq import merge

def merge_sort(seq):
 if len(seq) <= 1:
 return m
 else:  
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])
 return list(merge(left, right))  #heapq.merge()

if __name__=="__main__":
 seq = [1,3,6,2,4]
 print merge_sort(seq)

Eine ausführlichere Einführung in die Implementierungsschritte des Merge-Sort-Algorithmus in der Python-Programmierung finden Sie auf der chinesischen PHP-Website!