python 快速排序 + 一行实现

Python 快速排序 + 一行实现

快排往往是面试中出现频率最高的一个算法。当然，不仅仅考快排实现，还会问快排适用的场景呀，如何优化快排呀，它的时间复杂度和空间复杂度呀等等…

首先来看一下快排的实现原理：

简而言之：首先任意选择一个基准值，可以为首位，中间，甚至是尾部，把基准值从列表中分离出去，然后遍历列表元素，依次比较，如果当前值小于基准值的话，就放到基准值的左边，如果大于等于基准值的话，就放到基准值的右边。这样一轮下来，就可以确定基准值的位置了。接着分别对左边和右边部分进行同样的递归处理。

运用的是分而治之的思想，将问题分成小问题解决。采用递归，先分解后合并。

代码：

def quicksort(List):
   if len(List) < 2:
      return List
   mid = List[len(List)//2]
   List.remove(mid)
   left,right = [],[]
   for i in List:
      if i < mid:
	     left.append(i)
	  else:
	     right.append(i)
   return quicksort(left)+[mid]+quicksort(right)

一行实现

test = [2,5,1,2,7,3,9,4]

quicksort = lambda test : test if len(test) < 2 else quicksort([item for item in test[1:] if item < test[0]]) + [test[0]] + quicksort([item for item in test[1:] if item >= test[0]])

注：使用lambda+列表推导一行实现

调用方式:quicksort(test),lambda相当于匿名函数，test为它所接受的参数

快速排序的时间复杂度：O（nlogn)

快速排序的空间复杂度：O（nlogn)，排序时需要另外申请空间，并且随着数列规模增大而增大。

快速排序的优缺点：

1.再面对特别大量的数据时，使用快排比较好，但随着分治次数增多，分区规模越来越小时，则应该替换为插入排序，插入排序在面对数据量小的时候有接近线性的时间复杂度。

2.快速排序时不稳定的排序，比如基准值的前后都存在与基准值相同的元素，那么相同值就会被放在一边，这样就打乱了之前的相对顺序。