本文接上一篇博客python實(shí)現(xiàn)的八大排序算法part1，將繼續(xù)使用python實(shí)現(xiàn)八大排序算法中的剩余四個(gè)：快速排序、堆排序、歸并排序、基數(shù)排序

5、快速排序

快速排序是通常被認(rèn)為在同數(shù)量級(jí)（O(nlog2n)）的排序方法中平均性能最好的。

算法思想：

已知一組無(wú)序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數(shù)據(jù)a[x]作為基準(zhǔn)。比較a[x]與其它數(shù)據(jù)并排序，使a[x]排在數(shù)據(jù)的第k位，并且使a[1]~a[k-1]中的每一個(gè)數(shù)據(jù)<a[x]，a[k+1]~a[n]中的每一個(gè)數(shù)據(jù)>a[x]，然后采用分治的策略分別對(duì)a[1]~a[k-1]和a[k+1]~a[n]兩組數(shù)據(jù)進(jìn)行快速排序。
優(yōu)點(diǎn)：極快，數(shù)據(jù)移動(dòng)少；
缺點(diǎn)：不穩(wěn)定。

python代碼實(shí)現(xiàn)：

def quick_sort(list):
  little = []
  pivotList = []
  large = []
  # 遞歸出口
  if len(list) <= 1:
    return list
  else:
    # 將第一個(gè)值做為基準(zhǔn)
    pivot = list[0]
    for i in list:
      # 將比基準(zhǔn)小的值放到less數(shù)列
      if i < pivot:
        little.append(i)
      # 將比基準(zhǔn)大的值放到more數(shù)列
      elif i > pivot:
        large.append(i)
      # 將和基準(zhǔn)相同的值保存在基準(zhǔn)數(shù)列
      else:
        pivotList.append(i)
    # 對(duì)less數(shù)列和more數(shù)列繼續(xù)進(jìn)行快速排序
    little = quick_sort(little)
    large = quick_sort(large)
    return little + pivotList + large

下面這段代碼出自《Python cookbook 第二版的三行實(shí)現(xiàn)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實(shí)現(xiàn)八大排序算法
'''
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])

運(yùn)行測(cè)試結(jié)果截圖：

好吧，還有更精簡(jiǎn)的語(yǔ)法糖，一行完事：

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]

若初始序列按關(guān)鍵碼有序或基本有序時(shí)，快排序反而蛻化為冒泡排序。為改進(jìn)之，通常以“三者取中法”來(lái)選取基準(zhǔn)記錄，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄。快速排序是一個(gè)不穩(wěn)定的排序方法。

在改進(jìn)算法中,我們將只對(duì)長(zhǎng)度大于k的子序列遞歸調(diào)用快速排序,讓原序列基本有序，然后再對(duì)整個(gè)基本有序序列用插入排序算法排序。實(shí)踐證明，改進(jìn)后的算法時(shí)間復(fù)雜度有所降低，且當(dāng)k取值為 8 左右時(shí),改進(jìn)算法的性能最佳。

6、堆排序（Heap Sort）

堆排序是一種樹(shù)形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。

優(yōu)點(diǎn) : 效率高
缺點(diǎn)：不穩(wěn)定

堆的定義下：具有n個(gè)元素的序列 （h1,h2,...,hn),當(dāng)且僅當(dāng)滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)時(shí)稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)（大頂堆）。完全二 叉樹(shù)可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根，其它為左子樹(shù)、右子樹(shù)。

算法思想：

初始時(shí)把要排序的數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹(shù)，調(diào)整它們的存儲(chǔ)序，使之成為一個(gè) 堆，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最大。然后將根節(jié)點(diǎn)與堆的最后一個(gè)節(jié)點(diǎn)交換。然后對(duì)前面(n-1)個(gè)數(shù)重新調(diào)整使之成為堆。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對(duì) 它們作交換，最后得到有n個(gè)節(jié)點(diǎn)的有序序列。從算法描述來(lái)看，堆排序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。

python代碼實(shí)現(xiàn)：

# -*- 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):# 調(diào)整堆
  lchild = 2 * i + 1;rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[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):# 創(chuàng)建堆
  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)

結(jié)果示例：

7、歸并排序

算法思想：

歸并（Merge）排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

歸并過(guò)程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1；否則將第二個(gè)有序表中的元素a[j]復(fù)制到r[k]中，并令j和k分別加上1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。

# -*- 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 < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  result += left[i:]
  result += right[j:]
  print(result)
  return result
def merge_sort(lists):# 歸并排序
  if len(lists) <= 1:
    return lists
  num = int(len(lists) / 2)
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)

程序結(jié)果示例：

8、桶排序/基數(shù)排序(Radix Sort)

優(yōu)點(diǎn)：快，效率最好能達(dá)到O(1)
缺點(diǎn)：

1.首先是空間復(fù)雜度比較高，需要的額外開(kāi)銷大。排序有兩個(gè)數(shù)組的空間開(kāi)銷，一個(gè)存放待排序數(shù)組，一個(gè)就是所謂的桶，比如待排序值是從0到m-1，那就需要m個(gè)桶，這個(gè)桶數(shù)組就要至少m個(gè)空間。

2.其次待排序的元素都要在一定的范圍內(nèi)等等。

算法思想：

是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的陣列內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
簡(jiǎn)單來(lái)說(shuō)，就是把數(shù)據(jù)分組，放在一個(gè)個(gè)的桶中，然后對(duì)每個(gè)桶里面的在進(jìn)行排序。
例如要對(duì)大小為[1..1000]范圍內(nèi)的n個(gè)整數(shù)A[1..n]排序

首先，可以把桶大小設(shè)為10，這樣就有100個(gè)桶了，具體而言，設(shè)集合B[1]存儲(chǔ)[1..10]的整數(shù)，集合B[2]存儲(chǔ) (10..20]的整數(shù)，……集合B[i]存儲(chǔ)( (i-1)*10, i*10]的整數(shù)，i = 1,2,..100?？偣灿?100個(gè)桶。

然后，對(duì)A[1..n]從頭到尾掃描一遍，把每個(gè)A[i]放入對(duì)應(yīng)的桶B[j]中。 再對(duì)這100個(gè)桶中每個(gè)桶里的數(shù)字排序，這時(shí)可用冒泡，選擇，乃至快排，一般來(lái)說(shuō)任 何排序法都可以。

最后，依次輸出每個(gè)桶里面的數(shù)字，且每個(gè)桶中的數(shù)字從小到大輸出，這 樣就得到所有數(shù)字排好序的一個(gè)序列了。

假設(shè)有n個(gè)數(shù)字，有m個(gè)桶，如果數(shù)字是平均分布的，則每個(gè)桶里面平均有n/m個(gè)數(shù)字。如果

對(duì)每個(gè)桶中的數(shù)字采用快速排序，那么整個(gè)算法的復(fù)雜度是

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

從上式看出，當(dāng)m接近n的時(shí)候，桶排序復(fù)雜度接近O(n)

當(dāng)然，以上復(fù)雜度的計(jì)算是基于輸入的n個(gè)數(shù)字是平均分布這個(gè)假設(shè)的。這個(gè)假設(shè)是很強(qiáng)的 ，實(shí)際應(yīng)用中效果并沒(méi)有這么好。如果所有的數(shù)字都落在同一個(gè)桶中，那就退化成一般的排序了。

python代碼實(shí)現(xiàn)：

# -*- 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]
#因?yàn)榱斜頂?shù)據(jù)范圍在100以內(nèi)，所以將使用十個(gè)桶來(lái)進(jìn)行排序
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

程序運(yùn)行測(cè)試結(jié)果：

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論