Maison développement back-end Tutoriel Python Python实现的数据结构与算法之快速排序详解

Python实现的数据结构与算法之快速排序详解

Jun 06, 2016 am 11:25 AM
python 快速排序 数据结构 算法

本文实例讲述了Python实现的数据结构与算法之快速排序。分享给大家供大家参考。具体分析如下:

一、概述

快速排序(quick sort)是一种分治排序算法。该算法首先 选取 一个划分元素(partition element,有时又称为pivot);接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分)、划分元素pivot、right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上;然后分别对left和right两个部分进行 递归排序

其中,划分元素的 选取 直接影响到快速排序算法的效率,通常选择列表的第一个元素或者中间元素或者最后一个元素作为划分元素,当然也有更复杂的选择方式;划分 过程根据划分元素重排列表,是快速排序算法的关键所在,该过程的原理示意图如下:

快速排序算法的优点是:原位排序(只使用很小的辅助栈),平均情况下的时间复杂度为 O(n log n)。快速排序算法的缺点是:它是不稳定的排序算法,最坏情况下的时间复杂度为 O(n2)。

二、Python实现

1、标准实现

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

#!/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

Copier après la connexion

2、Pythonic实现

1

2

3

4

5

6

7

#!/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]])

Copier après la connexion

对比 标准实现 可以看出,Pythonic实现 更简洁、更直观、更酷。但需要指出的是,Pythonic实现 使用了Python中的 列表解析 (List Comprehension,也叫列表展开、列表推导),每一次 递归排序 都会产生新的列表,因此失去了快速排序算法本来的 原位排序 的优点。

三、算法测试

1

2

3

4

5

6

7

8

9

10

#!/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)))

Copier après la connexion

运行结果:

1

2

3

4

5

$ 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]

Copier après la connexion

希望本文所述对大家的Python程序设计有所帮助。

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

Article chaud

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

Article chaud

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

Tags d'article chaud

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 télécharger Deepseek Xiaomi Comment télécharger Deepseek Xiaomi Feb 19, 2025 pm 05:27 PM

Comment télécharger Deepseek Xiaomi

Implémentation d'algorithmes d'apprentissage automatique en C++ : défis et solutions courants Implémentation d'algorithmes d'apprentissage automatique en C++ : défis et solutions courants Jun 03, 2024 pm 01:25 PM

Implémentation d'algorithmes d'apprentissage automatique en C++ : défis et solutions courants

Google AI annonce Gemini 1.5 Pro et Gemma 2 pour les développeurs Google AI annonce Gemini 1.5 Pro et Gemma 2 pour les développeurs Jul 01, 2024 am 07:22 AM

Google AI annonce Gemini 1.5 Pro et Gemma 2 pour les développeurs

Algorithme de détection amélioré : pour la détection de cibles dans des images de télédétection optique haute résolution Algorithme de détection amélioré : pour la détection de cibles dans des images de télédétection optique haute résolution Jun 06, 2024 pm 12:33 PM

Algorithme de détection amélioré : pour la détection de cibles dans des images de télédétection optique haute résolution

Comment lui demandez-vous Deepseek Comment lui demandez-vous Deepseek Feb 19, 2025 pm 04:42 PM

Comment lui demandez-vous Deepseek

Quel logiciel est NET40 ? Quel logiciel est NET40 ? May 10, 2024 am 01:12 AM

Quel logiciel est NET40 ?

Comment rechercher Deepseek Comment rechercher Deepseek Feb 19, 2025 pm 05:18 PM

Comment rechercher Deepseek

Comment programmer Deepseek Comment programmer Deepseek Feb 19, 2025 pm 05:36 PM

Comment programmer Deepseek

See all articles