Python实现快速排序算法

cencenhai

快速排序(QuickSort)

1、算法思想
    　快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

（1） 分治法的基本思想
    　分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

（2）快速排序的基本思想
    　 设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
 

2、快速排序算法QuickSort


 

  1 def qsort(lst):
2  """快速排序，选第1个数据为关键数据"""
3  if lst == []:
4      return []
5  else:
6      l = [i for i in lst if i < lst[0]]
7      m = [i for i in lst if i == lst[0]]
8      r = [i for i in lst if i > lst[0]]
9      return qsort(l) + m + qsort(r)