快速排序（Python实现）

基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
下面这个图可以描述算法的实现过程：

时间复杂度

快速排序是一种不稳定的排序方法，平均时间复杂度为O (nlogn)，最坏情况和冒泡排序差不多，为O（n²）。

Python实现

# 简洁的实现方法
def quicksort(array):
  if len(array) < 2:
    return array
  else:
    pivot = array[0]
    less = [i for i in array[1:] if i <= pivot]
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3]) # 结果：[2, 3, 5, 10]

# 比较容易理解的实现方法
def quick(list):
    if len(list) < 2:
        return list
    else:
        left = i = 0
        j = len(list) - 1
        
        while i != j:
            while list[j] >= list[left] and i < j:
                j -= 1

            while list[i] <= list[left] and i < j:
                i += 1
            
            if i < j:
                list[i], list[j] = list[j], list[i]
        list[i], list[left] = list[left],  list[i]
        return quick(list[left:i]) + [list[i]] + quick(list[i+1:])

注意理解：上面的第二种方法，挑选了左侧第一个数作为参考，内部循环则从对面，即列表末尾开始查找，因为如果从左侧开始查找，当满足条件i=j退出循环时，list[i]会比list[left]大，交换之后违反了左边小右边大的原则。

该实例中涉及Python的一个称作列表推导表达式的语法糖用法，即在for循环中嵌套使用if和else语句。例如：

oldList = [12, 3, 4, 6, 7, 13, 21]
newList = [x for x in oldList if x%2 == 0]
print newList # 结果：[12, 4, 6]

想了解更多Python语法糖知识，请参考：Python语法糖系列