Maison développement back-end Tutoriel Python Résumé de huit algorithmes de tri en Python (Partie 2)

Résumé de huit algorithmes de tri en Python (Partie 2)

Sep 16, 2017 am 10:14 AM
python 排序

Cet article présente principalement en détail la deuxième partie des huit algorithmes de tri implémentés en Python. Il a une certaine valeur de référence. Les amis intéressés peuvent s'y référer

Cet article est la suite du blog python précédent, partie 1 de. les huit algorithmes de tri implémentés continueront à utiliser python pour implémenter les quatre autres algorithmes de tri : tri rapide, tri par tas, tri par fusion, tri par base

5, tri rapide

Le tri rapide est généralement considéré comme ayant la meilleure performance moyenne parmi les méthodes de tri du même ordre de grandeur (O(nlog2n)).

Idée algorithmique :

Nous connaissons un ensemble de données non ordonnées a[1], a[2],...a[n], qui doivent être classées par ordre croissant. Premièrement, toutes les données a[x] sont prises comme référence. Comparez a[x] avec d'autres données et triez-les de manière à ce que a[x] soit classé à la kème position des données, et placez chaque donnée dans a[1]~a[k-1] a[x], puis utilisez la stratégie diviser pour régner pour a[1]~a[k-1] et a[k+1]~a respectivement [n]Triez rapidement deux ensembles de données.
Avantages : extrêmement rapide, moins de mouvements de données
Inconvénients : instable ;

Implémentation du code Python :


def quick_sort(list):
  little = []
  pivotList = []
  large = []
  # 递归出口
  if len(list) <= 1:
    return list
  else:
    # 将第一个值做为基准
    pivot = list[0]
    for i in list:
      # 将比基准小的值放到less数列
      if i < pivot:
        little.append(i)
      # 将比基准大的值放到more数列
      elif i > pivot:
        large.append(i)
      # 将和基准相同的值保存在基准数列
      else:
        pivotList.append(i)
    # 对less数列和more数列继续进行快速排序
    little = quick_sort(little)
    large = quick_sort(large)
    return little + pivotList + large
Copier après la connexion

Le code suivant provient des trois lignes du "Python Cookbook Second Edition" pour implémenter le tri rapide Python.


#!/usr/bin/env python
#coding:utf-8
&#39;&#39;&#39;
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123.com
desc:python实现八大排序算法
&#39;&#39;&#39;
lst = [65,568,9,23,4,34,65,8,6,9]
def quick_sort(list):
  if len(list) <= 1:
    return list
  else:
    pivot = list[0]
    return quick_sort([x for x in list[1:] if x < pivot]) + \
        [pivot] + \
        quick_sort([x for x in list[1:] if x >= pivot])
Copier après la connexion

Capture d'écran des résultats du test en cours d'exécution :

Résumé de huit algorithmes de tri en Python (Partie 2)

D'accord, il y a un sucre syntaxique plus rationalisé, une ligne Terminé :

quick_sort = lambda xs : ( (len(xs) <= 1 et [xs]) ou [ quick_sort( [x for x in xs[1:] if x < xs [0]] ) + [xs[0]] + quick_sort( [x pour x dans xs[1:] if x >= xs[0]] ) ] )[0]

Si la séquence initiale est ordonnée par clé ou fondamentalement ordonnée, le tri rapide dégénérera en tri à bulles. Afin de l'améliorer, la « méthode trois en un » est généralement utilisée pour sélectionner l'enregistrement de référence, c'est-à-dire que les trois clés d'enregistrement centrées sur les deux extrémités et le point médian de l'intervalle de tri sont ajustées en tant qu'enregistrement de point d'appui. Le tri rapide est une méthode de tri instable.

Dans l'algorithme amélioré, nous appellerons de manière récursive le tri rapide uniquement sur les sous-séquences d'une longueur supérieure à k pour rendre la séquence d'origine fondamentalement ordonnée, puis utiliserons l'algorithme de tri par insertion pour trier toute la séquence ordonnée de base. La pratique a prouvé que la complexité temporelle de l'algorithme amélioré a été réduite, et lorsque la valeur de k est d'environ 8, l'algorithme amélioré présente les meilleures performances.

6. Tri par tas

Le tri par tas est un tri par sélection arborescente, qui constitue une amélioration efficace du tri par sélection directe.

Avantages : Haute efficacité
Inconvénients : instabilité

Sous la définition du tas : une séquence de n éléments (h1, h2,...,hn), quand Et il est appelé uniquement lorsqu'il satisfait (hi>=h2i,hi>=2i+1) ou (hi<=h2i,hi<=2i+1) (i=1,2,...,n/2) tas . Seuls les tas qui remplissent la première condition sont abordés ici. Il ressort de la définition d'un tas que l'élément supérieur du tas (c'est-à-dire le premier élément) doit être l'élément le plus grand (grand tas supérieur). Un arbre binaire complet peut représenter la structure du tas de manière très intuitive. Le sommet du tas est la racine, et les autres sont le sous-arbre gauche et le sous-arbre droit.

Idée algorithmique :

Initialement, la séquence de nombres à trier est considérée comme un arbre binaire stocké séquentiellement, et leur ordre de stockage est ajusté pour en faire un tas. Le nombre de nœuds racine dans le tas est le plus grand. Échangez ensuite le nœud racine avec le dernier nœud du tas. Réajustez ensuite les nombres précédents (n-1) pour former un tas. Et ainsi de suite, jusqu'à ce qu'il y ait un tas avec seulement deux nœuds, et qu'ils soient échangés, et finalement une séquence ordonnée de n nœuds est obtenue. D'après la description de l'algorithme, le tri du tas nécessite deux processus, l'un consiste à établir le tas et l'autre à échanger les positions entre le haut du tas et le dernier élément du tas. Le tri par tas se compose donc de deux fonctions. L'une est la fonction de pénétration pour construire le tas, et l'autre est la fonction permettant d'appeler à plusieurs reprises la fonction de pénétration pour implémenter le tri.

Implémentation du code python :


# -*- coding: UTF-8 -*-
&#39;&#39;&#39;
Created on 2017年9月2日
Running environment:win7.x86_64 eclipse python3
@author: Lockey
&#39;&#39;&#39;
lst = [65,568,9,23,4,34,65,8,6,9]
def adjust_heap(lists, i, size):# 调整堆
  lchild = 2 * i + 1;rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild
    if max != i:
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size)
def build_heap(lists, size):# 创建堆
  halfsize = int(size/2)
  for i in range(0, halfsize)[::-1]:
    adjust_heap(lists, i, size)
def heap_sort(lists):# 堆排序
  size = len(lists)
  build_heap(lists, size)
  for i in range(0, size)[::-1]:
    lists[0], lists[i] = lists[i], lists[0]
    adjust_heap(lists, 0, i)
    print(lists)
Copier après la connexion

Exemple de résultat :

Résumé de huit algorithmes de tri en Python (Partie 2)

7. Tri par fusion

Idée d'algorithme :

Le tri par fusion est un algorithme de tri efficace basé sur l'opération de fusion. L'algorithme utilise la méthode diviser pour régner. Une application très typique. Fusionnez les sous-séquences déjà ordonnées pour obtenir une séquence complètement ordonnée ; c'est-à-dire que vous devez d'abord rendre chaque sous-séquence ordonnée, puis ordonner les segments de la sous-séquence. Si deux listes ordonnées sont fusionnées en une seule liste ordonnée, on parle de fusion bidirectionnelle.

Le processus de fusion est le suivant : comparez les tailles de a[i] et a[j], si a[i]≤a[j], copiez l'élément a[i] dans la première liste ordonnée dans r [k], et ajoutez 1 à i et k respectivement ; sinon, copiez l'élément a[j] dans la deuxième liste ordonnée dans r[k], et ajoutez 1 à j et k respectivement. Ce cycle continue jusqu'à l'un des éléments ordonnés. lists est récupéré, puis les éléments restants de l’autre liste ordonnée sont copiés dans les cellules de r de l’indice k à l’indice t. Nous utilisons généralement la récursion pour implémenter l'algorithme de tri par fusion. Nous divisons d'abord l'intervalle à trier [s, t] en deux au milieu, puis trions la sous-plage de gauche, puis trions la sous-plage de droite et enfin utilisons a. opération de fusion entre l'intervalle gauche et l'intervalle droit Fusionner en intervalles ordonnés [s,t].


# -*- coding: UTF-8 -*-
&#39;&#39;&#39;
Created on 2017年9月2日
Running environment:win7.x86_64 eclipse python3
@author: Lockey
&#39;&#39;&#39;
lst = [65,568,9,23,4,34,65,8,6,9]
def merge(left, right):
  i, j = 0, 0
  result = []
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  result += left[i:]
  result += right[j:]
  print(result)
  return result
def merge_sort(lists):# 归并排序
  if len(lists) <= 1:
    return lists
  num = int(len(lists) / 2)
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)
Copier après la connexion

Exemple de résultats du programme :

Résumé de huit algorithmes de tri en Python (Partie 2)

8、桶排序/基数排序(Radix Sort)

优点:快,效率最好能达到O(1)
缺点:

1.首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

2.其次待排序的元素都要在一定的范围内等等。

算法思想:

是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

首先,可以把桶大小设为10,这样就有100个桶了,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储 (10..20]的整数,……集合B[i]存储( (i-1)*10, i*10]的整数,i = 1,2,..100。总共有 100个桶。

然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任 何排序法都可以。

最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这 样就得到所有数字排好序的一个序列了。

假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序,那么整个算法的复杂度是

O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

从上式看出,当m接近n的时候,桶排序复杂度接近O(n)

当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。

python代码实现:


# -*- coding: UTF-8 -*-
&#39;&#39;&#39;
Created on 2017年9月2日
Running environment:win7.x86_64 eclipse python3
@author: Lockey
&#39;&#39;&#39;
import math
lst = [65,56,9,23,84,34,8,6,9,54,11]
#因为列表数据范围在100以内,所以将使用十个桶来进行排序
def radix_sort(lists, radix=10):
  k = int(math.ceil(math.log(max(lists), radix)))
  bucket = [[] for i in range(radix)]
  for i in range(1, k+1):
    for j in lists:
      gg = int(j/(radix**(i-1))) % (radix**i)
      bucket[gg].append(j)
    del lists[:]
    for z in bucket:
      lists += z
      del z[:]
      print(lists)
  return lists
Copier après la connexion

程序运行测试结果:

Résumé de huit algorithmes de tri en Python (Partie 2)

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 de ce site Web
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

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Comment intégrer efficacement les services Node.js ou Python sous l'architecture LAMP? Comment intégrer efficacement les services Node.js ou Python sous l'architecture LAMP? Apr 01, 2025 pm 02:48 PM

De nombreux développeurs de sites Web sont confrontés au problème de l'intégration de Node.js ou des services Python sous l'architecture de lampe: la lampe existante (Linux Apache MySQL PHP) a besoin d'un site Web ...

Quelle est la raison pour laquelle les fichiers de stockage persistants de pipeline ne peuvent pas être écrits lors de l'utilisation du robot Scapy? Quelle est la raison pour laquelle les fichiers de stockage persistants de pipeline ne peuvent pas être écrits lors de l'utilisation du robot Scapy? Apr 01, 2025 pm 04:03 PM

Lorsque vous utilisez Scapy Crawler, la raison pour laquelle les fichiers de stockage persistants ne peuvent pas être écrits? Discussion Lorsque vous apprenez à utiliser Scapy Crawler pour les robots de données, vous rencontrez souvent un ...

Python multiplateform de bureau de bureau de bureau: quelle bibliothèque GUI est la meilleure pour vous? Python multiplateform de bureau de bureau de bureau: quelle bibliothèque GUI est la meilleure pour vous? Apr 01, 2025 pm 05:24 PM

Choix de la bibliothèque de développement d'applications de bureau multiplateforme Python De nombreux développeurs Python souhaitent développer des applications de bureau pouvant s'exécuter sur Windows et Linux Systems ...

Quelle est la raison pour laquelle le pool de processus Python gère les demandes TCP simultanées et fait coincé le client? Quelle est la raison pour laquelle le pool de processus Python gère les demandes TCP simultanées et fait coincé le client? Apr 01, 2025 pm 04:09 PM

Python Process Pool gère les demandes TCP simultanées qui font coincé le client. Lorsque vous utilisez Python pour la programmation réseau, il est crucial de gérer efficacement les demandes TCP simultanées. ...

Comment afficher les fonctions originales encapsulées en interne par Python Functools.Partial Objet? Comment afficher les fonctions originales encapsulées en interne par Python Functools.Partial Objet? Apr 01, 2025 pm 04:15 PM

Explorez profondément la méthode de visualisation de Python Functools.Partial Objet dans Functools.Partial en utilisant Python ...

Dessin graphique de sablier Python: comment éviter les erreurs variables non définies? Dessin graphique de sablier Python: comment éviter les erreurs variables non définies? Apr 01, 2025 pm 06:27 PM

Précision avec Python: Source de sablier Dessin graphique et vérification d'entrée Cet article résoudra le problème de définition variable rencontré par un novice Python dans le programme de dessin graphique de sablier. Code...

Comment optimiser le traitement des images à haute résolution dans Python pour trouver des zones circulaires blanches précises? Comment optimiser le traitement des images à haute résolution dans Python pour trouver des zones circulaires blanches précises? Apr 01, 2025 pm 06:12 PM

Comment gérer les images haute résolution à Python pour trouver des zones blanches? Traitement d'une image haute résolution de 9000x7000 pixels, comment trouver avec précision deux de l'image ...

Comment compter et trier efficacement de grands ensembles de données de produit dans Python? Comment compter et trier efficacement de grands ensembles de données de produit dans Python? Apr 01, 2025 pm 08:03 PM

Conversion et statistiques de données: traitement efficace des grands ensembles de données Cet article introduira en détail comment convertir une liste de données contenant des informations sur le produit en une autre contenant ...

See all articles