Heim  >  Artikel  >  Backend-Entwicklung  >  Python implementiert die Blasensortierung

Python implementiert die Blasensortierung

高洛峰
高洛峰Original
2016-10-19 17:23:161378Durchsuche

Python-Algorithmus - Python implementiert die Blasensortierung

Das Funktionsprinzip der Blasensortierung:

Vergleichen Sie benachbarte Elemente. Wenn das erste größer als das zweite ist, tauschen Sie beide aus.

Machen Sie dasselbe für jedes Paar benachbarter Elemente, beginnend mit dem ersten Paar und endend mit dem letzten Paar. Zu diesem Zeitpunkt sollte das letzte Element die größte Zahl sein.

Wiederholen Sie die obigen Schritte für alle Elemente außer dem letzten.

Wiederholen Sie die obigen Schritte jedes Mal für immer weniger Elemente, bis keine Zahlenpaare mehr zum Vergleichen vorhanden sind.


Beispielcode

# -*- Kodierung: utf-8 -*-


def bubble_sort(seq, cmp=cmp):

"""Blasensortierung, der Pseudocode lautet wie folgt:

BUBBLESORT(A)

1 für i ← 1 zur Länge [A]

2 tun für j ← Länge[A] bis i 1

3 tun, wenn A[j]

4 dann tausche A[j] ↔ A[j-1]


T(n) = θ(n^2)


Args:

seq (Sequenz): ein Sequenzobjekt cmp (Funktion): standardmäßig die integrierte Funktion cmp() 🎜> Eine sortierte Liste

"""

if (seq == None):

return None

length = len(seq)

für i im Bereich (Länge):

für j im Bereich (Länge- 1, i, -1):

wenn seq [j]

seq[j], seq[j-1] = seq[j-1 ], seq[j]

return seq

if __name__ == '__main__':


import random, timeit


items = range(10000)

random.shuffle(items)


def test_sorted():

print (items)

sorted_items = sorted(items)

print(sorted_items)

def test_bubble_sort():

print(items)

sorted_items = bubble_sort(items)

print(sorted_items)

test_methods = [test_sorted, test_bubble_sort]

für test in test_methods:

name = test.__name__ # test.func_name

t = timeit .Timer(name '()', 'from __main__ import ' name)

print(name ' braucht Zeit : %f' % t.timeit(1))

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
Vorheriger Artikel:Python-AlgorithmusNächster Artikel:Python-Algorithmus