總結有關python八大排序演算法（下）

這篇文章主要為大家詳細介紹了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[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) = xs[0]] ) ] )[0]

#若初始序列依關鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以「三者取中法」來選取基準記錄，即將排序區間的兩個端點與中點三個記錄關鍵碼居中的調整為支點記錄。快速排序是一個不穩定的排序方法。 ######在改進演算法中,我們將只對長度大於k的子序列遞歸調用快速排序,讓原序列基本有序，然後再對整個基本有序序列用插入排序演算法排序。實踐證明，改進後的演算法時間複雜度有所降低，且當k取值為 8 左右時,改進演算法的性能最佳。 #########6、堆排序（Heap Sort）#########堆排序是一種樹狀選擇排序，是直接選擇排序的有效改進。 #########優點: 效率高###缺點：不穩定######堆的定義下：具有n個元素的序列（h1,h2,...,hn),當且僅當滿足（hi>=h2i,hi>=2i+1）或（hi

8、桶排序/基数排序(Radix Sort)

优点：快，效率最好能达到O(1)
缺点：

1.首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。

2.其次待排序的元素都要在一定的范围内等等。

算法思想：

是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

首先，可以把桶大小设为10，这样就有100个桶了，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储 (10..20]的整数，……集合B[i]存储( (i-1)*10, i*10]的整数，i = 1,2,..100。总共有 100个桶。

然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任 何排序法都可以。

最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这 样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序，那么整个算法的复杂度是

O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

从上式看出，当m接近n的时候，桶排序复杂度接近O(n)

当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

python代码实现：

# -*- coding: UTF-8 -*-
'''
Created on 2017年9月2日
Running environment：win7.x86_64 eclipse python3
@author: Lockey
'''
import math
lst = [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

程序运行测试结果：

以上是總結有關python八大排序演算法（下）的詳細內容。更多資訊請關注PHP中文網其他相關文章！