简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
Heim > Backend-Entwicklung > Python-Tutorial > Hauptteil

Python实现快速排序算法及去重的快速排序的简单示例

WBOY
Freigeben： 2016-07-06 13:29:49
Original
1643 Leute haben es durchsucht

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

现在通过一个实例来说明快排。

比如有一个数组：

6 2 4 5 3
Nach dem Login kopieren

第一步：选取一个基准数，不要被这个名词吓到了，你可以把它看作是一个比较大小的数，因为排序就是比较大小，

比如我选取最后一个数3为基准数，依次把数组的数和3比较，比3小的放左边，比3大的放右边，这样有如下结果：

2 3 6 4 5
Nach dem Login kopieren

第二步：判断区间个数，经过第一步后左边区间只有一个数了，没有数字再和它比较了，因此不需要重复操作，右边区间还有：

6 4 5
Nach dem Login kopieren

重复第一步，选取5作为基准数，得到比较结果：

4 5 6
Nach dem Login kopieren

这样左右两边区间都只有一个数了，这就标志着排序完成，最后把所有区间合并就得到排序结果：

2 3 4 5 6
Nach dem Login kopieren

def quick_sort(array):
  less = []; greater = []
  if len(array) <= 1:
    return array
  pivot = array.pop()
  for x in array:
    if x <= pivot: less.append(x)
    else: greater.append(x)
  return quick_sort(less) + [pivot] + quick_sort(greater)
list = [2,4,2,6,7,8,1]
Nach dem Login kopieren

print quick_sort(list)
Nach dem Login kopieren

[1, 2, 2, 4, 6, 7, 8]
Nach dem Login kopieren

相比C、C#、JAVA之类的是不是简单多了^.^

TIP：去重的快速排序
如下, 只需要把集合修改为单值元素,这里我们使用Python3来演示:

# -*- coding: utf-8 -*- 
  
import random 
 
L = [2, 3, 8, 4, 9, 5, 6, 5, 6, 10, 17, 11, 2] 
 
def qsort(L): 
  if len(L)<2: return L 
  pivot_element = random.choice(L) 
  small = [i for i in L if i< pivot_element] 
  #medium = [i for i in L if i==pivot_element] 
  large = [i for i in L if i> pivot_element] 
  return qsort(small) + [pivot_element] + qsort(large) 
 
print(qsort(L))
Nach dem Login kopieren

输出:

[2, 3, 4, 5, 6, 8, 9, 10, 11, 17]
Nach dem Login kopieren

也可以直接使用, 集合(set)进行排序和去重.

mylist = list(set(L)) #集合自动排序字符串
Nach dem Login kopieren

Verwandte Etiketten：
python 快速排序 排序 算法
Quelle：php.cn
Vorheriger Artikel：Linux上安装Python的PIL和Pillow库处理图片的实例教程 Nächster Artikel：Python中的字符串查找操作方法总结
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Artikel des Autors
Aktuelle Ausgaben
Wie führe ich ein Python-Skript aus HTML in Google Chrome aus? Ich erstelle eine Chrome-Erweiterung und möchte ein Python-Skript von meinem PC aus ausfüh...
Aus 2023-11-02 23:34:24
0
1
400
Warum wählen einige MySQL-Verbindungen nach dem Löschen + Einfügen alte Daten der MySQL-Datenbank aus? Ich habe ein Problem mit Sitzungen in meiner Python-/wsgiweb-Anwendung. Jeder Thread in de...
Aus 2023-10-30 12:37:20
0
2
229
Verwenden von Variablen zum Ausführen von SQL-Anweisungen in Python Ich habe den folgenden Python-Code: Cursor.execute("INSERTINTOtableVALUESvar1,var2,va...
Aus 2023-10-12 15:06:00
0
2
258
Den ternären Operator in Python verstehen [Duplikat] Ich wechsle derzeit von JavaScript zu Python und frage mich, ob Python einen ternären Oper...
Aus 2023-09-21 18:46:04
0
1
377
Wie man mit Python Zeichenfolgen mit angehängten Teilen abgleicht, diese jedoch nicht abgleicht, wenn die angehängten Teile unterschiedlich sind Wie kann man Zeichenfolgen mit angehängten Teilen abgleichen, sie aber nicht abgleichen, w...
Aus 2023-09-20 19:02:23
0
1
260
verwandte Themen
Mehr>
Beliebte Empfehlungen
Beliebte Tutorials
Mehr>
Verwandte Tutorials
Beliebte Empfehlungen
Aktuelle Kurse
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website：Online-PHP-Schulung für das Gemeinwohl，Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln！