python实现八大排序算法（2）

本文接上一篇博客python实现的八大排序算法part1，将继续使用python实现八大排序算法中的剩余四个：快速排序、堆排序、归并排序、基数排序

5、快速排序

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。

算法思想：

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据<a[x]，a[k+1]~a[n]中的每一个数据>a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。
优点：极快，数据移动少；
缺点：不稳定。

python代码实现：

def quick_sort(list):  little = []  pivotList = []  large = []  # 递归出口  if len(list) <= 1:    return list  else:    # 将第一个值做为基准    pivot = list[0]    for i in list:      # 将比基准小的值放到less数列      if i < pivot:        little.append(i)      # 将比基准大的值放到more数列      elif i > pivot:        large.append(i)      # 将和基准相同的值保存在基准数列      else:        pivotList.append(i)    # 对less数列和more数列继续进行快速排序    little = quick_sort(little)    large = quick_sort(large)    return little + pivotList + large

下面这段代码出自《Python cookbook 第二版的三行实现python快速排序。

#!/usr/bin/env python#coding:utf-8'''file:python-8sort.pydate:9/1/17 9:03 AMauthor:lockeyemail:lockey@123.comdesc:python实现八大排序算法'''lst = [65,568,9,23,4,34,65,8,6,9]def quick_sort(list):  if len(list) <= 1:    return list  else:    pivot = list[0]    return quick_sort([x for x in list[1:] if x < pivot]) + /        [pivot] + /        quick_sort([x for x in list[1:] if x >= pivot])

运行测试结果截图：

好吧，还有更精简的语法糖，一行完事：

quick_sort = lambda xs : ( (len(xs) <= 1 and [xs]) or [ quick_sort( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + quick_sort( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]

若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

在改进算法中,我们将只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。