Maison  >  Article  >  développement back-end  >  Résumé des méthodes d'implémentation des algorithmes de tri en python (code)

Résumé des méthodes d'implémentation des algorithmes de tri en python (code)

不言
不言original
2018-09-27 14:48:001857parcourir

Ce que cet article vous apporte est un résumé (code) de la méthode d'implémentation de l'algorithme de tri en Python. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

1. Tri par insertion : L'opération de base du tri par insertion consiste à insérer une donnée dans les données ordonnées qui ont été triées, de manière à obtenir une nouvelle donnée ordonnée avec le nombre plus un pour lequel l'algorithme est adapté. Tri d'une petite quantité de données ; traitez d'abord la première comme déjà triée, puis retirez la dernière et insérez-la au recto à chaque fois et triez-la

def insert_sort(ilist):
    for i in range(len(ilist)):
        for j in range(i):
            if ilist[i] < ilist[j]:
                ilist.insert(j, ilist.pop(i))
                break
    return ilist
 
ilist = insert_sort([4,5,6,7,3,2,6,9,8])
print ilist

2. Tri des bulles : il visite à plusieurs reprises Pour trier une séquence, comparez deux éléments à la fois et échangez-les s'ils sont dans le mauvais ordre. Le travail de visite du tableau est répété jusqu'à ce qu'aucun échange ne soit plus nécessaire, ce qui signifie que le tableau a été trié

def bubble_sort(blist):
    count = len(blist)
    for i in range(0, count):
        for j in range(i + 1, count):
            if blist[i] > blist[j]:
                blist[i], blist[j] = blist[j], blist[i]
    return blist
 
blist = bubble_sort([4,5,6,7,3,2,6,9,8])
print blist

3. Tri rapide : Divisez les données à trier en deux parties indépendantes via un seul tri pass , toutes les données d'une partie sont plus petites que toutes les données de l'autre partie, puis utilisez cette méthode pour trier rapidement les deux parties des données respectivement. L'ensemble du processus de tri peut être effectué de manière récursive, de sorte que les données entières deviennent. une séquence ordonnée

def quick_sort(qlist):
    if qlist == []:
        return []
    else:
        qfirst = qlist[0]
        qless = quick_sort([l for l in qlist[1:] if l < qfirst])
        qmore = quick_sort([m for m in qlist[1:] if m >= qfirst])
        return qless + [qfirst] + qmore
 
qlist = quick_sort([4,5,6,7,3,2,6,9,8])
print qlist

4. Tri par sélection : Dans le premier passage, sélectionnez le plus petit enregistrement parmi les enregistrements à trier r1 ~ r[n], et échangez-le avec r1 dans le deuxième passage, dans les enregistrements à trier r2~ Sélectionnez le plus petit enregistrement parmi r[n] et échangez-le avec r2 et ainsi de suite, le i-ième passage enregistre r[i] à trier ~ ; Sélectionnez le plus petit enregistrement parmi r[n] et échangez-le avec r[i], de sorte que la séquence ordonnée continue de croître jusqu'à ce que tout le tri soit terminé

def select_sort(slist):
    for i in range(len(slist)):
        x = i
        for j in range(i, len(slist)):
            if slist[j] < slist[x]:
                x = j
        slist[i], slist[x] = slist[x], slist[i]
    return slist
 
slist = select_sort([4,5,6,7,3,2,6,9,8])
print slist

Recherche binaire : principalement effectuée en divisant par. 2 Recherche de jugement;

#!/usr/bin/python
# -*- coding: utf-8 -*-
#二分查找,用于在较大的数据列表中查询某个值,考虑到元素比较多,单纯的遍历会造成内存压力过大,考虑使用二分查找
#二分查找的关键在于查询中间值,将需要查找的值与中间值进行比较,然后确定查找方向
def binary_search(data_source,find_n):
    #取中位数
    mid=int(len(data_source)/2)

    if len(data_source)>=1:
        if data_source[mid]>find_n:  #中位数大于要查找的数,则要查找的数在左半部分,继续调用二分算法进行查找
            binary_search(data_source[:mid],find_n)
        elif data_source[mid]<find_n:  #中位数小于要查找的数,则要查找的数在右半部分
            binary_search(data_source[mid:],find_n)
        else:   #中位数等于要查找的数
            print("找到了:",data_source[mid])

    else:
        print("没有找到")


if __name__=="__main__":
    data=list(range(3,1600))
    binary_search(data,400)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn