Tri rapide Python, algorithme de tri par insertion, explication détaillée des exemples de tri personnalisé

Cet article présente principalement Python pour implémenter des algorithmes de tri rapide et de tri par insertion et des exemples de tri personnalisé. Le tri personnalisé utilise les fonctions de tri et de tri de Python. Les amis dans le besoin peuvent s'y référer

. 1. Tri rapide

Le tri rapide est une amélioration du tri à bulles. Proposé par CAR Hoare en 1962. Son idée de base est de diviser les données à trier en deux parties indépendantes via un tri. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie, puis d'utiliser cette méthode pour séparer rapidement les deux parties des données. . Tri, l'ensemble du processus de tri peut être effectué de manière récursive , de sorte que l'ensemble des données devienne une séquence ordonnée.

Tri rapide, implémentation récursive

def quick_sort(num_list):
  """
  快速排序
  """
  if num_list == []:
    return num_list
  smallList = []
  bigList = []
  middleElement = num_list[0]
  for i in num_list[1:]:
    if i <= middleElement:
      smallList.append(i)
    else:
      bigList.append(i)
  return quick_sort(smallList)+[middleElement]+quick_sort(bigList)

2. Tri par insertion

La description de l'algorithme de tri par insertion est un algorithme de tri simple et intuitif . Il fonctionne en construisant une séquence ordonnée. Pour les données non triées, il analyse d'arrière en avant dans la séquence triée pour trouver la position correspondante et l'insérer. Dans la mise en œuvre du tri par insertion, le tri sur place est généralement utilisé (c'est-à-dire un tri qui utilise uniquement l'espace supplémentaire O(1). Par conséquent, pendant le processus d'analyse d'arrière en avant, les éléments triés doivent être triés de manière répétée et progressive). décalé vers l'arrière, fournissant un espace d'insertion pour le dernier élément.

Tri par insertion

def insert_sort(num_list):
  """
  插入排序
  """
  for i in range(len(num_list)-1):
    for j in range(i+1, len(num_list)):
      if num_list[i]>num_list[j]:
        num_list[i],num_list[j] = num_list[j],num_list[i]
  return num_list

3. Le tri personnalisé
peut être réalisé en utilisant la clé de sort() ou sorted().

Les exemples sont les suivants :

def sort_key(obj):
  sorted_list = [4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
  return sorted_list.index(obj)
 
 
if name == 'main':
  print sorted(range(10), key=sort_key)
 
# 输出结果如下
[4, 2, 5, 9, 7, 8, 1, 3, 6, 0]

# Utilisez la position index du mot-clé dans la liste pour effectuer un tri personnalisé

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!