Python實現快速排序算法及去重的快速排序的簡單示例

quick sort快速排序是一種再基礎不過的排序算法,使用Python代碼寫起來相當簡潔,這里我們就來看一下Python實現快速排序算法及去重的快速排序的簡單示例:

快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經常被采用。
該方法的基本思想是：
1．先從數列中取出一個數作為基準數。
2．分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。
3．再對左右區間重復第二步，直到各區間只有一個數。
現在通過一個實例來說明快排。
比如有一個數組：    
6 2 4 5 3
第一步：選取一個基準數，不要被這個名詞嚇到了，你可以把它看作是一個比較大小的數，因為排序就是比較大小，
比如我選取最后一個數3為基準數，依次把數組的數和3比較，比3小的放左邊，比3大的放右邊，這樣有如下結果：    
2 3 6 4 5
第二步：判斷區間個數，經過第一步后左邊區間只有一個數了，沒有數字再和它比較了，因此不需要重復操作，右邊區間還有：    
6 4 5
重復第一步，選取5作為基準數，得到比較結果：    
4 5 6
這樣左右兩邊區間都只有一個數了，這就標志著排序完成，最后把所有區間合并就得到排序結果：    
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)進行排序和去重.    
mylist = list(set(L)) #集合自動排序字符串