Python实现的数据结构与算法之快速排序详解
本文实例讲述了Python实现的数据结构与算法之快速排序。分享给大家供大家参考。具体分析如下:
一、概述
快速排序(quick sort)是一种分治排序算法。该算法首先 选取 一个划分元素(partition element,有时又称为pivot);接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分)、划分元素pivot、right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上;然后分别对left和right两个部分进行 递归排序。
其中,划分元素的 选取 直接影响到快速排序算法的效率,通常选择列表的第一个元素或者中间元素或者最后一个元素作为划分元素,当然也有更复杂的选择方式;划分 过程根据划分元素重排列表,是快速排序算法的关键所在,该过程的原理示意图如下:
快速排序算法的优点是:原位排序(只使用很小的辅助栈),平均情况下的时间复杂度为 O(n log n)。快速排序算法的缺点是:它是不稳定的排序算法,最坏情况下的时间复杂度为 O(n2)。
二、Python实现
1、标准实现
#!/usr/bin/env python # -*- coding: utf-8 -*- def stdQuicksort(L): qsort(L, 0, len(L) - 1) def qsort(L, first, last): if first < last: split = partition(L, first, last) qsort(L, first, split - 1) qsort(L, split + 1, last) def partition(L, first, last): # 选取列表中的第一个元素作为划分元素 pivot = L[first] leftmark = first + 1 rightmark = last while True: while L[leftmark] <= pivot: # 如果列表中存在与划分元素pivot相等的元素,让它位于left部分 # 以下检测用于划分元素pivot是列表中的最大元素时, #防止leftmark越界 if leftmark == rightmark: break leftmark += 1 while L[rightmark] > pivot: # 这里不需要检测,划分元素pivot是列表中的最小元素时, # rightmark会自动停在first处 rightmark -= 1 if leftmark < rightmark: # 此时,leftmark处的元素大于pivot, #而rightmark处的元素小于等于pivot,交换二者 L[leftmark], L[rightmark] = L[rightmark], L[leftmark] else: break # 交换first处的划分元素与rightmark处的元素 L[first], L[rightmark] = L[rightmark], L[first] # 返回划分元素pivot的最终位置 return rightmark
2、Pythonic实现
#!/usr/bin/env python # -*- coding: utf-8 -*- def pycQuicksort(L): if len(L) <= 1: return L return pycQuicksort([x for x in L if x < L[0]]) + \ [x for x in L if x == L[0]] + \ pycQuicksort([x for x in L if x > L[0]])
对比 标准实现 可以看出,Pythonic实现 更简洁、更直观、更酷。但需要指出的是,Pythonic实现 使用了Python中的 列表解析 (List Comprehension,也叫列表展开、列表推导),每一次 递归排序 都会产生新的列表,因此失去了快速排序算法本来的 原位排序 的优点。
三、算法测试
#!/usr/bin/env python # -*- coding: utf-8 -*- if __name__ == '__main__': L = [54, 26, 93, 17, 77, 31, 44, 55, 20] M = L[:] print('before stdQuicksort: ' + str(L)) stdQuicksort(L) print('after stdQuicksort: ' + str(L)) print('before pycQuicksort: ' + str(M)) print('after pycQuicksort: ' + str(pycQuicksort(M)))
运行结果:
$ python testquicksort.py before stdQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20] after stdQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93] before pycQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20] after pycQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93]
希望本文所述对大家的Python程序设计有所帮助。

Outils d'IA chauds

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

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

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

Video Face Swap
Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

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

PHP convient au développement Web et au prototypage rapide, et Python convient à la science des données et à l'apprentissage automatique. 1.Php est utilisé pour le développement Web dynamique, avec une syntaxe simple et adapté pour un développement rapide. 2. Python a une syntaxe concise, convient à plusieurs champs et a un écosystème de bibliothèque solide.

PHP est principalement la programmation procédurale, mais prend également en charge la programmation orientée objet (POO); Python prend en charge une variété de paradigmes, y compris la POO, la programmation fonctionnelle et procédurale. PHP convient au développement Web, et Python convient à une variété d'applications telles que l'analyse des données et l'apprentissage automatique.

VS Code peut fonctionner sur Windows 8, mais l'expérience peut ne pas être excellente. Assurez-vous d'abord que le système a été mis à jour sur le dernier correctif, puis téléchargez le package d'installation VS Code qui correspond à l'architecture du système et l'installez comme invité. Après l'installation, sachez que certaines extensions peuvent être incompatibles avec Windows 8 et doivent rechercher des extensions alternatives ou utiliser de nouveaux systèmes Windows dans une machine virtuelle. Installez les extensions nécessaires pour vérifier si elles fonctionnent correctement. Bien que le code VS soit possible sur Windows 8, il est recommandé de passer à un système Windows plus récent pour une meilleure expérience de développement et une meilleure sécurité.

Les extensions de code vs posent des risques malveillants, tels que la cachette de code malveillant, l'exploitation des vulnérabilités et la masturbation comme des extensions légitimes. Les méthodes pour identifier les extensions malveillantes comprennent: la vérification des éditeurs, la lecture des commentaires, la vérification du code et l'installation avec prudence. Les mesures de sécurité comprennent également: la sensibilisation à la sécurité, les bonnes habitudes, les mises à jour régulières et les logiciels antivirus.

Dans VS Code, vous pouvez exécuter le programme dans le terminal via les étapes suivantes: Préparez le code et ouvrez le terminal intégré pour vous assurer que le répertoire de code est cohérent avec le répertoire de travail du terminal. Sélectionnez la commande Run en fonction du langage de programmation (tel que Python de Python your_file_name.py) pour vérifier s'il s'exécute avec succès et résoudre les erreurs. Utilisez le débogueur pour améliorer l'efficacité du débogage.

VS Code peut être utilisé pour écrire Python et fournit de nombreuses fonctionnalités qui en font un outil idéal pour développer des applications Python. Il permet aux utilisateurs de: installer des extensions Python pour obtenir des fonctions telles que la réalisation du code, la mise en évidence de la syntaxe et le débogage. Utilisez le débogueur pour suivre le code étape par étape, trouver et corriger les erreurs. Intégrez Git pour le contrôle de version. Utilisez des outils de mise en forme de code pour maintenir la cohérence du code. Utilisez l'outil de liaison pour repérer les problèmes potentiels à l'avance.

VS Code est disponible sur Mac. Il a des extensions puissantes, l'intégration GIT, le terminal et le débogueur, et offre également une multitude d'options de configuration. Cependant, pour des projets particulièrement importants ou un développement hautement professionnel, le code vs peut avoir des performances ou des limitations fonctionnelles.

Python convient plus aux débutants, avec une courbe d'apprentissage en douceur et une syntaxe concise; JavaScript convient au développement frontal, avec une courbe d'apprentissage abrupte et une syntaxe flexible. 1. La syntaxe Python est intuitive et adaptée à la science des données et au développement back-end. 2. JavaScript est flexible et largement utilisé dans la programmation frontale et côté serveur.
