面試咱不怕——快速排序

說到算法，面試的時候，如果碰到，必然會有這麼一些題目。其中只要有排序，必然就會有這個應用最廣的排序算法。沒錯，我說的就是快速排序，一般暱稱快排。

為啥都喜歡考快排？因為快排是一個相對比較均衡的排序算法，在各種情況下，都能基本保持比較穩定的時間複雜度。因此，快排在實際應用之中，使用非常廣泛。

一般快排都是語言標準庫內置實現，所以不需要自己寫。但是，如果面試碰到了，如果不是經常寫，總得想想。這裡，我給出非常簡短和清晰的實現，很方便在面試時寫出來，比一般的偽代碼還簡單。畢竟，面試主要考的是瞭解算法和思路，不是真的碼代碼。

這裡給出史上最簡短的快排寫法。

<code>
def
 
qsort(arr):
    
if
 
len(arr)==0:
         
return
  
arr
    
return
 
qsort([i
 
for
 
i
 
in
 
arr
 
if
 
i>arr[0]])+[i
 
for
 
i
 
in
 
arr
 
if
 
i==arr[0]]+qsort([i
 
for
 
i
 
in
 
arr
 
if
 
i
qsort([4,6,2,6,2132,43,2,6,7,8,34])
[2132,
 
43
,
 
34 
,
 
8
,
 
7
,
 
6
,
 
6
,
 
6
,
 
4
,
 
2
,
 
2
]
/<code>

原理就不多說了，相信準備面試的大家都清楚。這裡python語法裡的列表生成式很簡單完成了列表的分治，把大於，等於和小於第一個數的元素分離開分別遞歸排序。當然這裡性能肯定不多做考慮，主要是為了清晰。快排的算法其實就這麼簡單，當然性能優化是大坑，不多說了。