Python實(shí)現(xiàn)快速排序算法及去重的快速排序的簡(jiǎn)單示例
快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用。
該方法的基本思想是：
1．先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)。
2．分區(qū)過(guò)程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)。
現(xiàn)在通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明快排。
比如有一個(gè)數(shù)組：
6 2 4 5 3
第一步：選取一個(gè)基準(zhǔn)數(shù)，不要被這個(gè)名詞嚇到了，你可以把它看作是一個(gè)比較大小的數(shù)，因?yàn)榕判蚓褪潜容^大小，
比如我選取最后一個(gè)數(shù)3為基準(zhǔn)數(shù)，依次把數(shù)組的數(shù)和3比較，比3小的放左邊，比3大的放右邊，這樣有如下結(jié)果：
2 3 6 4 5
第二步：判斷區(qū)間個(gè)數(shù)，經(jīng)過(guò)第一步后左邊區(qū)間只有一個(gè)數(shù)了，沒(méi)有數(shù)字再和它比較了，因此不需要重復(fù)操作，右邊區(qū)間還有：
6 4 5
重復(fù)第一步，選取5作為基準(zhǔn)數(shù)，得到比較結(jié)果：
4 5 6
這樣左右兩邊區(qū)間都只有一個(gè)數(shù)了，這就標(biāo)志著排序完成，最后把所有區(qū)間合并就得到排序結(jié)果：
2 3 4 5 6
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]
print quick_sort(list)
[1, 2, 2, 4, 6, 7, 8]
相比C、C#、JAVA之類的是不是簡(jiǎn)單多了^.^
TIP：去重的快速排序
如下, 只需要把集合修改為單值元素,這里我們使用Python3來(lái)演示:
# -*- 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))
輸出:
[2, 3, 4, 5, 6, 8, 9, 10, 11, 17]
也可以直接使用, 集合(set)進(jìn)行排序和去重.
mylist = list(set(L)) #集合自動(dòng)排序字符串
- python快速排序代碼實(shí)例
- Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之快速排序詳解
- Python實(shí)現(xiàn)快速排序和插入排序算法及自定義排序的示例
- 快速排序的四種python實(shí)現(xiàn)（推薦）
- 快速排序的算法思想及Python版快速排序的實(shí)現(xiàn)示例
- python實(shí)現(xiàn)快速排序的示例(二分法思想)
- javascript與Python快速排序?qū)嵗龑?duì)比
- python 二分查找和快速排序?qū)嵗斀?/a>
- Python編程二分法實(shí)現(xiàn)冒泡算法+快速排序代碼示例
- Python實(shí)現(xiàn)的插入排序，冒泡排序，快速排序，選擇排序算法示例
- Python一行代碼實(shí)現(xiàn)快速排序的方法
- Python實(shí)現(xiàn)快速排序的方法詳解
相關(guān)文章
在本篇文章中小編給大家分享的是關(guān)于解決python中0x80072ee2錯(cuò)誤的方法，需要的朋友們可以參考下。2020-07-07
這篇文章主要介紹了Python獲取百度熱搜的完整代碼,代碼簡(jiǎn)單易懂，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
Pandas之read_csv()讀取文件跳過(guò)報(bào)錯(cuò)行的解決
這篇文章主要介紹了Pandas之read_csv()讀取文件跳過(guò)報(bào)錯(cuò)行的解決，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-04-04
本文主要介紹了Python虛擬環(huán)境安裝及操作命令詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
這篇文章主要介紹了Python之列表的append()方法最容易踩的坑及解決，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
今天小編就為大家分享一篇pandas重新生成索引的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-11-11
使用Python的Twisted框架編寫(xiě)非阻塞程序的代碼示例
Twisted是基于異步模式的開(kāi)發(fā)框架,因而利用Twisted進(jìn)行非阻塞編程自然也是必會(huì)的用法,下面我們就來(lái)一起看一下使用Python的Twisted框架編寫(xiě)非阻塞程序的代碼示例:2016-05-05
這篇文章主要介紹了Python編寫(xiě)命令行腳本操作excel的方法，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的朋友可以參考一下2022-08-08
python如何發(fā)布自已pip項(xiàng)目的方法步驟
這篇文章主要介紹了python如何發(fā)布自已pip項(xiàng)目的方法步驟，方便大家學(xué)習(xí)，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-10-10
這篇文章主要介紹了字典中的值是列表問(wèn)題，先用value連成一個(gè)str，最后用str.split()作一個(gè)轉(zhuǎn)換，生成一個(gè)列表.看了python cookbook，上面正好有一個(gè)recipe講到如何處理這樣的問(wèn)題2013-03-03