Eine Zusammenfassung gängiger zentralisierter Sortieralgorithmen
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:', numsNach dem Login kopieren
Stabil, zeitliche Komplexität O(nlog n)
Einfügungssortierung
Der Code lautet wie folgt:
#!/usr/bin/python
import sys
def insert_sort(a):
Nach dem Login kopieren
''''' Einfügungssortierung
Es gibt eine bereits geordnete Datensequenz und es ist erforderlich, eine Zahl in diese sortierte Datensequenz einzufügen.
Es ist jedoch erforderlich, dass diese Datensequenz nach dem Einfügen in Ordnung bleibt. Am Anfang ist offensichtlich ein Element in Ordnung, dann fügen Sie ein
-Element an der entsprechenden Position ein, und fügen Sie dann das dritte Element ein und so weiter
'''
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:', numsNach dem Login kopieren
Stabile, zeitliche Komplexität O(n^2)
Um die Werte zweier Elemente auszutauschen, kann man in Python so schreiben: a, b = b, a. Tatsächlich liegt dies an der Zuweisung. Die linke und rechte Seite des Symbols sind Tupel
(hier sollte betont werden, 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):
Nach dem Login kopieren
''''' Auswahlsortierung
Bei jedem Durchgang wird das kleinste (oder größte) Element aus den zu sortierenden Datenelementen ausgewählt,
Reihenfolge Platzieren Sie es bei das Ende des sortierten Arrays, bis alle zu sortierenden Datenelemente erschöpft sind.
Die Auswahlsortierung ist eine instabile Sortiermethode.
' ' '
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:',ANach dem Login kopieren
Instabil, zeitliche Komplexität O(n^2)
Hügelsortierung
Hügelsortierung Hill-Sortierung, auch als absteigender inkrementeller Sortieralgorithmus bekannt, 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. Sortieren Sie zuerst innerhalb jeder Gruppe;
Nehmen Sie dann das zweite Inkrement d2def 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:',ANach dem Login kopieren
ist instabil, die durchschnittliche Zeitkomplexität ist O(nlogn) und die schlechteste Zeit ist O(n^s)1Heap-Sortierung (Heap-Sortierung)
Die Definition von „Heap“: Im „Heap“ mit einem Startindex von 0:
Der rechte untergeordnete Knoten des Knotens i ist an Position 2 * i 24) Der übergeordnete Knoten von Knoten i befindet sich an Position floor( (i - 1) / 2): Beachten Sie, dass floor die „Rundungs“-Operation darstellt
Eigenschaften des Heaps:
jedes Knotens Der Schlüsselwert muss immer größer (oder kleiner) sein als sein übergeordneter Knoten
„Max 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 seine Position erreichen, 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 ist übergeordneter Knoten.
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:',ANach dem Login kopieren
不稳定，时间复杂度 O(nlog n)
快速排序
快速排序算法和合并排序算法一样，也是基于分治模式。对子数组A[p...r]快速排序的分治过程的三个步骤为：
分解：把数组A[p...r]分为A[p...q-1]与A[q+1...r]两部分，其中A[p...q-1]中的每个元素都小于等于A[q]而A[q+1...r]中的每个元素都大于等于A[q]；
解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]进行排序；
合并：因为两个子数组是就地排序的，所以不需要额外的操作。
对于划分partition 每一轮迭代的开始，x=A[r], 对于任何数组下标k，有：
1) 如果p≤k≤i，则A[k]≤x。
2) 如果i+1≤k≤j-1，则A[k]>x。
3) 如果k=r，则A[k]=x。
代码如下：
#!/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:',ANach dem Login kopieren
不稳定，时间复杂度 最理想 O(nlogn)最差时间O(n^2)
说下python中的序列：
列表、元组和字符串都是序列，但是序列是什么，它们为什么如此特别呢？序列的两个主要特点是索引操作符和切片操作符。索引操作符让我们可以从序列中抓取一个特定项目。切片操作符让我们能够获取序列的一个切片，即一部分序列,如：a = ['aa','bb','cc'], print a[0] 为索引操作，print a[0:2]为切片操作。
