算法思路

快速排序差不多是面试中问的最多的一种排序算法了，快排是比较容易理解的，核心思路就是，选取一个数作为基准，将原来的列表分为两个部分，一部分全部小于这个基准数，另外一部分全部大于这个基准数，然后呢再按照这个方法对划分出来的两部分继续做同样的操作，直到无法划分的时候排序也就完成了。

以数组[3,2,1,5,4,6]为例，其排序过程如下图所示。

关于时间复杂度问题， 平均复杂度n log(n) 最坏情况 n^2，以长度为16的list为例：

代码实现

方法一：

按照上述的思路可分为两个部分来写代码，一部分是使用递归，一部分是调整位置。

def partition(nums, left, right):    temp = nums[left]    while left < right:        while left < right and nums[right] >= temp:   # 从右往左搜索比基准值小            right -= 1   # 没有则往右走一位        nums[left] = nums[right]  # 找到了比基准值小的则调整顺序        while left < right and nums[left] <= temp:  # 从左往右找比基准大的数            left += 1        nums[right] = nums[left]    nums[left] = temp   # 交换完成之后归位    return left  # 返回基准值的位置def quick_sort(nums, left, right):    if left < right:        mid = partition(nums, left, right)        quick_sort(nums, left, mid - 1)   # 比基准值小的一部分再次进行快排        quick_sort(nums, mid + 1, right)  # 比基准值大的一部分

方法二：

上面这种呢是在原有的list进行变换，如果不考虑原有变换还有一种更直观的方法来实现，使用列表生成式来实现，只不过在数据量很大的时候会占用更多的空间。不考虑交换操作，直接简单粗暴的把list分割成两部分。

def quick_sort(nums):    if len(nums) <= 1:        return nums    pivot = nums[len(nums)//2]    left = [x for x in nums if x < pivot]    middle = [x for x in nums if x == pivot]    right = [x for x in nums if x > pivot]    return quick_sort(left) + middle + quick_sort(right)