快速排序(quicksort)的采用了分治的策略。
分治策略指的是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快排的基本思想是：在序列中找一个划分值，通过一趟排序将未排序的序列排序成独立的两个部分，其中左边部分序列都比划分值小，右边部分的序列比划分值大，此时划分值的位置已确认，然后再对这两个序列按照同样的方法进行排序，从而达到整个序列都有序的目的。
快排的动画演示快排的思路快排的python实现先看一个简单的python快排实现
代码示例deffake_quick_sort(arr):
iflen(arr)2:
returnarr
else:
pivot=arr[0]
left=[xforxinarr[1:]ifx=pivot]
right=[xforxinarr[1:]ifxpivot]
returnfake_quick_sort(left)+[pivot]+fake_quick_sort(right)
这段代码最关键的是pivot这个参数，这段代码里取序列的第一个元素，然后以这个元素为分组的基准，利用列表解析式使得它左边的值都比它小，右边的值都比它大。然后再分别对这些序列进行递归排序。这段代码虽然短小利于理解，但是其效率很低，所以函数名前面有个“fake”，主要体现在以下方面：
分组基准的选取过于随便，不一定可以取到列表的中间值
空间复杂度大，使用了两个列表解析式，而且每次选取进行比较时需要遍历整个序列。
若序列长度过于小(比如只有几个元素)，快排效率就不如插入排序了。
递归影响性能，最好进行优化。
下面用Python写一个C风格的快排(这里可以体会到快排的精髓)，当然了，其实没有完全解决上面的问题，有情趣的读者可以自己试试：
defquick_sort(arr,left,right):
ifleftright:
pivot=partition(arr,left,right)
quick_sort(arr,left,pivot-1)
quick_sort(arr,pivot+1,right)
returnarr
defpartition(arr,left,right):
pivotkey=arr[left]
whileleftright:
whileleftrightandarr[right]=pivotkey:
right-=1
arr[left]=arr[right]
whileleftrightandarr[left]=pivotkey:
left+=1
arr[right]=arr[left]
arr[left]=pivotkey
returnleft
快排的算法复杂度时间复杂度（平均）空间复杂度稳定性O(nlogn)O(logn)~O(n)不稳定·END·
更多精彩，请白癜风的发病原因有哪些预防白癜风的方法有哪些