python实现八大排序算法（2）
需积分: 0 79 浏览量
2020-09-21
04:09:50
上传
评论
收藏 198KB PDF 举报
python实现八大排序算法（实现八大排序算法（2））
主要为大家详细介绍了python实现八大排序算法的第二篇，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
本文接上一篇博客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.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123.com
desc: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]
若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录
评论0
最新资源