快捷導(dǎo)航

Python實(shí)現(xiàn)快速排序算法及去重的快速排序的簡(jiǎn)單示例

更新時(shí)間：2016年06月26日 16:53:18 作者：j_hao104

quick sort快速排序是一種再基礎(chǔ)不過(guò)的排序算法,使用Python代碼寫(xiě)起來(lái)相當(dāng)簡(jiǎn)潔,這里我們就來(lái)看一下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)排序字符串

您可能感興趣的文章:

相關(guān)文章

Python?隊(duì)列Queue和PriorityQueue解析
這篇文章主要介紹了Python?隊(duì)列Queue和PriorityQueue，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2022-09-09
python爬蟲(chóng)爬取快手視頻多線程下載功能
這篇文章主要介紹了python爬蟲(chóng)爬取快手視頻多線程下載功能，非常不錯(cuò)，具有參考借鑒價(jià)值,需要的朋友可以參考下
2018-02-02
用pycharm開(kāi)發(fā)django項(xiàng)目示例代碼
這篇文章主要介紹了用pycharm開(kāi)發(fā)django項(xiàng)目示例，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
2018-10-10
Python如何對(duì)圖像補(bǔ)全并分割成多塊補(bǔ)丁
這篇文章主要介紹了Python如何對(duì)圖像補(bǔ)全并分割成多塊補(bǔ)丁，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2022-05-05
Python數(shù)據(jù)類型相互轉(zhuǎn)換
當(dāng)涉及數(shù)據(jù)類型轉(zhuǎn)換時(shí),Python提供了多種內(nèi)置函數(shù)來(lái)執(zhí)行不同類型之間的轉(zhuǎn)換,本文主要介紹了Python數(shù)據(jù)類型相互轉(zhuǎn)換,具有一定的參考價(jià)值,感興趣的可以了解一下
2023-09-09
Python實(shí)現(xiàn)將MP4視頻轉(zhuǎn)化為GIF圖像
與靜態(tài)圖像相比，動(dòng)態(tài)的?GIF?圖片更能吸引各位讀者的注意力，還可以提供更生動(dòng)、有趣和引人入勝的內(nèi)容，本文為大家介紹了Python將MP4視頻轉(zhuǎn)化為GIF圖像的方法，需要的可以參考下
2023-06-06
python裝飾器三種裝飾模式的簡(jiǎn)單分析
這篇文章主要介紹了python裝飾器的三種裝飾模式，幫助大家更好的理解和學(xué)習(xí)python 裝飾器，感興趣的朋友可以了解下
2020-09-09
Python?一篇文章看懂Python集合與字典數(shù)據(jù)類型
集合并不是一種數(shù)據(jù)處理類型，而是一種中間類型。集合(set)是一個(gè)無(wú)序、不重復(fù)的元素序列，經(jīng)常被用來(lái)處理兩個(gè)列表進(jìn)行交并差的處理性。本文將詳細(xì)講解集合的一些常用方法，感興趣的可以了解一下
2022-03-03
Python實(shí)現(xiàn)讀取文件的方法總結(jié)
這篇文章主要為大家詳細(xì)介紹了Python中實(shí)現(xiàn)讀取文件效果的幾種方法總結(jié)，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下
2022-09-09
python操作MySQL數(shù)據(jù)庫(kù)的方法分享
堅(jiān)持每天學(xué)一點(diǎn)，每天積累一點(diǎn)點(diǎn)，作為自己每天的業(yè)余收獲，這個(gè)文章是我在吃飯的期間寫(xiě)的，利用自己零散的時(shí)間學(xué)了一下python操作MYSQL，所以整理一下
2012-05-05