总结有关python八大排序算法（下）

def quick_sort(list):  little = []  pivotList = []  large = []  # 递归出口  if len(list)  pivot:        large.append(i)      # 将和基准相同的值保存在基准数列      else:        pivotList.append(i)    # 对less数列和more数列继续进行快速排序    little = quick_sort(little)    large = quick_sort(large)    return little + pivotList + large

#!/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) = pivot])

# -*- coding: UTF-8 -*-'''Created on 2017年9月2日Running environment：win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def adjust_heap(lists, i, size):# 调整堆  lchild = 2 * i + 1;rchild = 2 * i + 2  max = i  if i  lists[max]:      max = lchild    if rchild  lists[max]:      max = rchild    if max != i:      lists[max], lists[i] = lists[i], lists[max]      adjust_heap(lists, max, size)def build_heap(lists, size):# 创建堆  halfsize = int(size/2)  for i in range(0, halfsize)[::-1]:    adjust_heap(lists, i, size)def heap_sort(lists):# 堆排序  size = len(lists)  build_heap(lists, size)  for i in range(0, size)[::-1]:    lists[0], lists[i] = lists[i], lists[0]    adjust_heap(lists, 0, i)    print(lists)

# -*- coding: UTF-8 -*-'''Created on 2017年9月2日Running environment：win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def merge(left, right):  i, j = 0, 0  result = []  while i <p>程序结果示例：</p><p><img title="" alt="这里写图片描述" src="https://img.php.cn/upload/article/000/000/007/0c0a685b5253a798876c44ccfc992bfd-2.png"></p><p><strong>8、桶排序/基数排序(Radix Sort)</strong></p><p>优点：快，效率最好能达到O(1) <br>缺点：</p><p>1.首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。</p><p>2.其次待排序的元素都要在一定的范围内等等。<br></p><p>算法思想：</p><p><span>立即学习</span>“<a href="https://pan.quark.cn/s/00968c3c2c15"   style="max-width:90%" rel="nofollow" target="_blank">Python免费学习笔记（深入）</a>”；</p><p>是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。<br>简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。<br>例如要对大小为[1..1000]范围内的n个整数A[1..n]排序</p><p>首先，可以把桶大小设为10，这样就有100个桶了，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储 (10..20]的整数，……集合B[i]存储( (i-1)*10, i*10]的整数，i = 1,2,..100。总共有 100个桶。</p><p>然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任 何排序法都可以。</p><p>最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这 样就得到所有数字排好序的一个序列了。</p><p>假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果</p><p>对每个桶中的数字采用快速排序，那么整个算法的复杂度是</p><p><span style="color: #800000">O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)</span></p><p>从上式看出，当m接近n的时候，桶排序复杂度接近O(n)</p><p>当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。</p><p>python代码实现：</p><p class="jb51code"><br></p><pre class="brush:py;"># -*- coding: UTF-8 -*-'''Created on 2017年9月2日Running environment：win7.x86_64 eclipse python3@author: Lockey'''import mathlst = [65,56,9,23,84,34,8,6,9,54,11]#因为列表数据范围在100以内，所以将使用十个桶来进行排序def radix_sort(lists, radix=10):  k = int(math.ceil(math.log(max(lists), radix)))  bucket = [[] for i in range(radix)]  for i in range(1, k+1):    for j in lists:      gg = int(j/(radix**(i-1))) % (radix**i)      bucket[gg].append(j)    del lists[:]    for z in bucket:      lists += z      del z[:]      print(lists)  return lists