Python實現(xiàn)快速排序算法及去重的快速排序的簡單示例
快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用。
該方法的基本思想是：
1．先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)。
2．分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。
現(xiàn)在通過一個實例來說明快排。
比如有一個數(shù)組：
6 2 4 5 3
第一步：選取一個基準(zhǔn)數(shù)，不要被這個名詞嚇到了，你可以把它看作是一個比較大小的數(shù)，因為排序就是比較大小，
比如我選取最后一個數(shù)3為基準(zhǔn)數(shù)，依次把數(shù)組的數(shù)和3比較，比3小的放左邊，比3大的放右邊，這樣有如下結(jié)果：
2 3 6 4 5
第二步：判斷區(qū)間個數(shù)，經(jīng)過第一步后左邊區(qū)間只有一個數(shù)了，沒有數(shù)字再和它比較了，因此不需要重復(fù)操作，右邊區(qū)間還有：
6 4 5
重復(fù)第一步，選取5作為基準(zhǔn)數(shù)，得到比較結(jié)果：
4 5 6
這樣左右兩邊區(qū)間都只有一個數(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之類的是不是簡單多了^.^
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))
輸出:
[2, 3, 4, 5, 6, 8, 9, 10, 11, 17]
也可以直接使用, 集合(set)進(jìn)行排序和去重.
mylist = list(set(L)) #集合自動排序字符串
- python快速排序代碼實例
- Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之快速排序詳解
- Python實現(xiàn)快速排序和插入排序算法及自定義排序的示例
- 快速排序的四種python實現(xiàn)（推薦）
- 快速排序的算法思想及Python版快速排序的實現(xiàn)示例
- python實現(xiàn)快速排序的示例(二分法思想)
- javascript與Python快速排序?qū)嵗龑Ρ?/a>
- python 二分查找和快速排序?qū)嵗斀?/a>
- Python編程二分法實現(xiàn)冒泡算法+快速排序代碼示例
- Python實現(xiàn)的插入排序，冒泡排序，快速排序，選擇排序算法示例
- Python一行代碼實現(xiàn)快速排序的方法
- Python實現(xiàn)快速排序的方法詳解
相關(guān)文章
Python?隊列Queue和PriorityQueue解析
這篇文章主要介紹了Python?隊列Queue和PriorityQueue，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-09-09
這篇文章主要介紹了python爬蟲爬取快手視頻多線程下載功能，非常不錯，具有參考借鑒價值,需要的朋友可以參考下2018-02-02
這篇文章主要介紹了用pycharm開發(fā)django項目示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-10-10
這篇文章主要介紹了Python如何對圖像補全并分割成多塊補丁，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-05-05
Python數(shù)據(jù)類型相互轉(zhuǎn)換
當(dāng)涉及數(shù)據(jù)類型轉(zhuǎn)換時,Python提供了多種內(nèi)置函數(shù)來執(zhí)行不同類型之間的轉(zhuǎn)換,本文主要介紹了Python數(shù)據(jù)類型相互轉(zhuǎn)換,具有一定的參考價值,感興趣的可以了解一下2023-09-09
Python實現(xiàn)將MP4視頻轉(zhuǎn)化為GIF圖像
與靜態(tài)圖像相比，動態(tài)的?GIF?圖片更能吸引各位讀者的注意力，還可以提供更生動、有趣和引人入勝的內(nèi)容，本文為大家介紹了Python將MP4視頻轉(zhuǎn)化為GIF圖像的方法，需要的可以參考下2023-06-06
這篇文章主要介紹了python裝飾器的三種裝飾模式，幫助大家更好的理解和學(xué)習(xí)python 裝飾器，感興趣的朋友可以了解下2020-09-09
Python?一篇文章看懂Python集合與字典數(shù)據(jù)類型
集合并不是一種數(shù)據(jù)處理類型，而是一種中間類型。集合(set)是一個無序、不重復(fù)的元素序列，經(jīng)常被用來處理兩個列表進(jìn)行交并差的處理性。本文將詳細(xì)講解集合的一些常用方法，感興趣的可以了解一下2022-03-03
這篇文章主要為大家詳細(xì)介紹了Python中實現(xiàn)讀取文件效果的幾種方法總結(jié)，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-09-09
python操作MySQL數(shù)據(jù)庫的方法分享
堅持每天學(xué)一點，每天積累一點點，作為自己每天的業(yè)余收獲，這個文章是我在吃飯的期間寫的，利用自己零散的時間學(xué)了一下python操作MYSQL，所以整理一下2012-05-05