面试咱不怕——快速排序

说到算法，面试的时候，如果碰到，必然会有这么一些题目。其中只要有排序，必然就会有这个应用最广的排序算法。没错，我说的就是快速排序，一般昵称快排。

为啥都喜欢考快排？因为快排是一个相对比较均衡的排序算法，在各种情况下，都能基本保持比较稳定的时间复杂度。因此，快排在实际应用之中，使用非常广泛。

一般快排都是语言标准库内置实现，所以不需要自己写。但是，如果面试碰到了，如果不是经常写，总得想想。这里，我给出非常简短和清晰的实现，很方便在面试时写出来，比一般的伪代码还简单。毕竟，面试主要考的是了解算法和思路，不是真的码代码。

这里给出史上最简短的快排写法。

<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语法里的列表生成式很简单完成了列表的分治，把大于，等于和小于第一个数的元素分离开分别递归排序。当然这里性能肯定不多做考虑，主要是为了清晰。快排的算法其实就这么简单，当然性能优化是大坑，不多说了。