Heim >Backend-Entwicklung >Python-Tutorial >Zusammenfassung und Beispiele des Python-Sortieralgorithmus
Zusammenfassung und Beispiele des Python-Sortieralgorithmus
- 高洛峰Original
- 2017-02-24 15:19:321755Durchsuche
Dieser Artikel stellt hauptsächlich die relevanten Informationen zur Zusammenfassung des Python-Sortieralgorithmus und detaillierte Beispiele vor. Freunde, die sie benötigen, können darauf verweisen
Es fasst die gängigen zentralisierten Sortieralgorithmen zusammen
Zusammenführungssortierung
Zusammenführungssortierung, auch Zusammenführungssortierung genannt, ist eine typische Anwendung der Divide-and-Conquer-Methode. Die Idee von „Teile und herrsche“ besteht darin, jedes Problem in kleine Probleme zu zerlegen, jedes kleine Problem zu lösen und sie dann zusammenzuführen.
Die spezifische Zusammenführungssortierung besteht darin, eine Menge ungeordneter Zahlen rekursiv in Unterelemente mit nur einem Element um n/2 zu zerlegen, und ein Element ist bereits sortiert. Anschließend werden diese geordneten Unterelemente zusammengeführt.
Der Zusammenführungsprozess besteht darin, zwei sortierte Teilsequenzen zu vergleichen, zuerst das kleinste Element in den beiden Teilsequenzen auszuwählen, dann die kleinste Teilsequenz der beiden Elemente auszuwählen und es aus der Teilsequenz zu entfernen
Entfernen und Zum endgültigen Ergebnissatz hinzufügen, bis die beiden Teilsequenzen zusammengeführt sind.
Der Code lautet wie folgt:
#!/usr/bin/python
import sys
def merge(nums, first, middle, last):
''''' merge '''
# 切片边界,左闭右开并且是了0为开始
lnums = nums[first:middle+1]
rnums = nums[middle+1:last+1]
lnums.append(sys.maxint)
rnums.append(sys.maxint)
l = 0
r = 0
for i in range(first, last+1):
if lnums[l] < rnums[r]:
nums[i] = lnums[l]
l+=1
else:
nums[i] = rnums[r]
r+=1
def merge_sort(nums, first, last):
''''' merge sort
merge_sort函数中传递的是下标，不是元素个数
'''
if first < last:
middle = (first + last)/2
merge_sort(nums, first, middle)
merge_sort(nums, middle+1, last)
merge(nums, first, middle,last)
if __name__ == '__main__':
nums = [10,8,4,-1,2,6,7,3]
print 'nums is:', nums
merge_sort(nums, 0, 7)
print 'merge sort:', nums
Stabil, zeitliche Komplexität O(nlog n)
Einfügung Der Code zum Sortieren
lautet wie folgt:
#!/usr/bin/python
importsys
definsert_sort(a):
''''' 插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，
但要求插入后此数据序列仍然有序。刚开始 一个元素显然有序，然后插入一
个元素到适当位置，然后再插入第三个元素，依次类推
'''
a_len = len(a)
if a_len = 0 and a[j] > key:
a[j+1] = a[j]
j-=1
a[j+1] = key
return a
if __name__ == '__main__':
nums = [10,8,4,-1,2,6,7,3]
print 'nums is:', nums
insert_sort(nums)
print 'insert sort:', nums
ist stabil und die Zeitkomplexität ist O(n^2)
Um die Werte zweier Elemente auszutauschen, können Sie dies in Python schreiben: a, b = b, a Tatsächlich liegt dies daran, dass die linke und rechte Seite des Zuweisungssymbole sind Tupel
(was hier betont werden muss, ist, dass Tupel in Python tatsächlich durch Kommas "," anstelle von Klammern getrennt werden).
Auswahlsortierung
Auswahlsortierung ist ein einfacher und intuitiver Sortieralgorithmus. So funktioniert es. Suchen Sie zunächst das kleinste (große) Element in der unsortierten Sequenz und speichern Sie es an der Startposition der
sortierten Sequenz. Suchen Sie dann weiterhin das kleinste (große) Element aus den verbleibenden unsortierten Elementen und Fügen Sie es dann in die sortierte Reihenfolge ein. Und so weiter, bis alle
-Elemente sortiert sind.
import sys
def select_sort(a):
''''' 选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
'''
a_len=len(a)
for i in range(a_len):#在0-n-1上依次选择相应大小的元素
min_index = i#记录最小元素的下标
for j in range(i+1, a_len):#查找最小值
if(a[j]<a[min_index]):
min_index=j
if min_index != i:#找到最小元素进行交换
a[i],a[min_index] = a[min_index],a[i]
if __name__ == '__main__':
A = [10, -3, 5, 7, 1, 3, 7]
print 'Before sort:',A
select_sort(A)
print 'After sort:',A
Instabil, zeitliche Komplexität O(n^2)
Hill-Sortierung
Hill-Sortierung, auch als absteigender inkrementeller Sortieralgorithmus bekannt. Hill-Sortierung ist ein instabiler Sortieralgorithmus. Diese Methode wird auch als reduzierende inkrementelle Sortierung bezeichnet, da DL. Shell wurde nach seinem Vorschlag im Jahr 1959 benannt.
Nehmen Sie zunächst eine Ganzzahl d1 kleiner als n als erstes Inkrement und teilen Sie alle Datensätze in der Datei in d1-Gruppen auf. Alle Datensätze, deren Abstand ein Vielfaches von d1 ist, werden in derselben Gruppe platziert. Erste Sortierung innerhalb jeder Gruppe;
Dann nehmen Sie das zweite Inkrement d2
import sys
def shell_sort(a):
''''' shell排序
'''
a_len=len(a)
gap=a_len/2#增量
while gap>0:
for i in range(a_len):#对同一个组进行选择排序
m=i
j=i+1
while j<a_len:
if a[j]<a[m]:
m=j
j+=gap#j增加gap
if m!=i:
a[m],a[i]=a[i],a[m]
gap/=2
if __name__ == '__main__':
A = [10, -3, 5, 7, 1, 3, 7]
print 'Before sort:',A
shell_sort(A)
print 'After sort:',A
Instabil, zeitliche Komplexität Durchschnittliche Zeit O(nlogn) Schlechteste Zeit O(n^s)1
Heap Sort (Heap Sort)
Die Definition von „Heap“: im „Heap“ mit ein Startindex von 0:
Der rechte untergeordnete Knoten von Knoten i befindet sich an Position 2 * i + 24) Der übergeordnete Knoten von Knoten i befindet sich an Position floor( (i – 1) / 2) : Beachten Sie den Boden stellt die „Rundungs“-Operation dar
Eigenschaften des Heaps:
Der Schlüsselwert jedes Knotens muss immer größer (oder kleiner) als sein übergeordneter Knoten sein
"Maximum Heap“:
Der Wurzelknoten des „Heaps“ speichert den Knoten mit dem größten Schlüsselwert. Das heißt, der Schlüsselwert jedes Knotens im „Heap“ ist immer größer als der seiner untergeordneten Knoten.
Nach oben verschieben, nach unten verschieben:
Wenn der Schlüsselwert eines Knotens größer als sein übergeordneter Knoten ist, müssen wir eine „Nach oben“-Operation durchführen, das heißt, wir verschieben den Knoten zu Die Position seines übergeordneten Knotens, und lassen Sie seinen übergeordneten Knoten zu seiner Position gehen, und dann beurteilen wir den Knoten weiter und hören nicht auf, uns nach oben zu bewegen, bis der Knoten nicht mehr größer als sein übergeordneter Knoten ist.
Jetzt werfen wir einen Blick auf den Vorgang „Nach unten verschieben“. Wenn wir den Schlüsselwert eines Knotens auf einen kleineren Wert ändern, müssen wir ihn „nach unten verschieben“.
Methode:
Wir erstellen zunächst einen maximalen Heap (Zeitkomplexität O(n)) und müssen dann jedes Mal nur den Wurzelknoten mit dem Knoten an der letzten Position austauschen, und Dann setzen Sie die letzte Eine Position wird ausgeschlossen, und dann wird der Heap des Wurzelknotens nach dem Austausch angepasst (Zeitkomplexität O(lgn)), dh der Wurzelknoten wird „nach unten verschoben“. Die Gesamtzeitkomplexität der Heap-Sortierung beträgt O(nlgn).
Der Code lautet wie folgt:
#!/usr/bin env python
# 数组编号从 0开始
def left(i):
return 2*i +1
def right(i):
return 2*i+2
#保持最大堆性质 使以i为根的子树成为最大堆
def max_heapify(A, i, heap_size):
if heap_size <= 0:
return
l = left(i)
r = right(i)
largest = i # 选出子节点中较大的节点
if l A[largest]:
largest = l
if r A[largest]:
largest = r
if i != largest :#说明当前节点不是最大的，下移
A[i], A[largest] = A[largest], A[i] #交换
max_heapify(A, largest, heap_size)#继续追踪下移的点
#print A
# 建堆
def bulid_max_heap(A):
heap_size = len(A)
if heap_size >1:
node = heap_size/2 -1
while node >= 0:
max_heapify(A, node, heap_size)
node -=1
# 堆排序 下标从0开始
def heap_sort(A):
bulid_max_heap(A)
heap_size = len(A)
i = heap_size - 1
while i > 0 :
A[0],A[i] = A[i], A[0] # 堆中的最大值存入数组适当的位置，并且进行交换
heap_size -=1 # heap 大小 递减 1
i -= 1 # 存放堆中最大值的下标递减 1
max_heapify(A, 0, heap_size)
if __name__ == '__main__' :
A = [10, -3, 5, 7, 1, 3, 7]
print 'Before sort:',A
heap_sort(A)
print 'After sort:',A
Instabile Zeitkomplexität O(nlog n)
Schnellsortierung
Der Schnellsortierungsalgorithmus basiert ebenso wie der Zusammenführungssortierungsalgorithmus auf dem Teilen-und-Herrsche-Modus. Die drei Schritte des Divide-and-Conquer-Prozesses zum schnellen Sortieren des Subarrays A[p…r] sind:
Zerlegung: Teilen Sie das Array A[p…r] in A[p…q-1] und A[ q+1…r], wobei jedes Element in A[p…q-1] kleiner oder gleich A[q] ist und jedes Element in A[q+1…r] größer oder gleich ist A[q ];
Lösung: Sortieren Sie die Subarrays A[p...q-1] und A[q+1...r] durch rekursiven Aufruf von Quick Sort; : Da die beiden Subarrays vor Ort sortiert werden, sind keine zusätzlichen Vorgänge erforderlich.
Für den Anfang jeder Iteration der Partitionspartition, x=A[r], für jeden Array-Index k gibt es:
1) Wenn p≤k≤i, dann A[ k]≤x.
2) Wenn i+1≤k≤j-1, dann A[k]>x.
3) Wenn k=r, dann A[k]=x.
Der Code lautet wie folgt:
#!/usr/bin/env python
# 快速排序
'''''
划分 使满足 以A[r]为基准对数组进行一个划分，比A[r]小的放在左边，
比A[r]大的放在右边
快速排序的分治partition过程有两种方法，
一种是上面所述的两个指针索引一前一后逐步向后扫描的方法,
另一种方法是两个指针从首位向中间扫描的方法。
'''
#p,r 是数组A的下标
def partition1(A, p ,r):
'''''
方法一，两个指针索引一前一后逐步向后扫描的方法
'''
x = A[r]
i = p-1
j = p
while j < r:
if A[j] < x:
i +=1
A[i], A[j] = A[j], A[i]
j += 1
A[i+1], A[r] = A[r], A[i+1]
return i+1
def partition2(A, p, r):
'''''
两个指针从首尾向中间扫描的方法
'''
i = p
j = r
x = A[p]
while i = x and i < j:
j -=1
A[i] = A[j]
while A[i]<=x and i < j:
i +=1
A[j] = A[i]
A[i] = x
return i
# quick sort
def quick_sort(A, p, r):
'''''
快速排序的最差时间复杂度为O(n2)，平时时间复杂度为O(nlgn)
'''
if p < r:
q = partition2(A, p, r)
quick_sort(A, p, q-1)
quick_sort(A, q+1, r)
if __name__ == '__main__':
A = [5,-4,6,3,7,11,1,2]
print 'Before sort:',A
quick_sort(A, 0, 7)
print 'After sort:',AInstabil, die beste Zeitkomplexität ist O(nlogn) und die schlechteste Zeit ist O(n^2)
Lassen Sie uns über Sequenzen in Python sprechen:
Listen, Tupel und Strings alles Sequenzen, aber was sind Sequenzen und warum sind sie so besonders? Die beiden Hauptmerkmale von Sequenzen sind der Indexierungsoperator und der Slicing-Operator. Mit dem Indexoperator können wir ein bestimmtes Element aus einer Sequenz abrufen. Mit dem Slice-Operator können wir einen Slice der Sequenz erhalten, dh einen Teil der Sequenz, wie zum Beispiel: a = ['aa', 'bb', 'cc'], print a[0] ist eine Indexoperation , drucken Sie a[0:2] für Slicing-Operationen.
Ich hoffe, durch diesen Artikel das Wissen über das Sortieren von Python-Algorithmen zu erlernen. Vielen Dank für Ihre Unterstützung dieser Website!
Weitere Artikel zu Zusammenfassungen und Beispielen des Python-Sortieralgorithmus finden Sie auf der chinesischen PHP-Website!