快捷導(dǎo)航

Python排序算法實(shí)例代碼

更新時(shí)間：2017年08月10日 08:28:44 作者：banananana

這篇文章主要為大家詳細(xì)介紹了Python實(shí)現(xiàn)排序算法的相關(guān)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

排序算法，下面算法均是使用Python實(shí)現(xiàn)：

插入排序

原理：循環(huán)一次就移動(dòng)一次元素到數(shù)組中正確的位置，通常使用在長度較小的數(shù)組的情況以及作為其它復(fù)雜排序算法的一部分，比如mergesort或quicksort。時(shí)間復(fù)雜度為 O(n2) 。

# 1nd: 兩兩交換
def insertion_sort(arr):
 for i in range(1, len(arr)):
  j = i
  while j >= 0 and arr[j-1] > arr[j]:
   arr[j], arr[j-1] = arr[j-1], arr[j]
   j -= 1
 return arr
# 2nd: 交換，最后處理沒交換的
def insertion_sort2(arr):
 for i in range(1, len(arr)):
  j = i-1
  key = arr[i]
  while j >= 0 and arr[j] > key:
   arr[j+1] = arr[j]
   j -= 1
  arr[j+1] = key
 return arr
# 3nd: 加速版本，利用已經(jīng)排好了序的進(jìn)行二分查找
def insertion_sort3(seq):
 for i in range(1, len(seq)):
  key = seq[i]
  # invariant: ``seq[:i]`` is sorted
  # find the least `low' such that ``seq[low]`` is not less then `key'.
  # Binary search in sorted sequence ``seq[low:up]``:
  low, up = 0, i
  while up > low:
   middle = (low + up) // 2
   if seq[middle] < key:
    low = middle + 1
   else:
    up = middle
  # insert key at position ``low``
  seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]
 return seq
# 4nd: 原理同上，使用bisect
import bisect
def insertion_sort4(seq):
 for i in range(1, len(seq)):
  bisect.insort(seq, seq.pop(i), 0, i) # 默認(rèn)插在相同元素的左邊
 return seq

選擇排序

原理：每一趟都選擇最小的值和當(dāng)前下標(biāo)的值進(jìn)行交換，適用在大型的數(shù)組，時(shí)間復(fù)雜度為 O(n2)

# 1nd: for
def select_sort(seq):
 for i in range(0, len(seq)):
  mi = i
  for j in range(i, len(seq)):
   if seq[j] < seq[mi]:
    mi = j
  seq[mi], seq[i] = seq[i], seq[mi]
 return seq
# 2nd: min
def select_sort2(seq):
 for i, x in enumerate(seq):
  mi = min(range(i, len(seq)), key=seq.__getitem__)
  seq[i], seq[mi] = seq[mi], x
 return seq

冒泡排序

原理：比較數(shù)組中兩兩相鄰的數(shù)，如果第一個(gè)大于第二個(gè)，就進(jìn)行交換，重復(fù)地走訪過要排序的數(shù)列，達(dá)到將最小的值移動(dòng)到最上面的目的，適用于小型數(shù)組，時(shí)間復(fù)雜度為O(n2)

def bubble_sort(seq):
 for i in range(len(seq)):
  for j in range(len(seq)-1-i):
   if seq[j] > seq[j+1]:
    seq[j], seq[j+1] = seq[j+1], seq[j]
 return seq
def bubble_sort2(seq):
 for i in range(0, len(seq)):
  for j in range(i + 1, len(seq)):
   if seq[i] > seq[j]:
    seq[i], seq[j] = seq[j], seq[i]
 return seq

快速排序

原理：從數(shù)組中選擇pivot，分成兩個(gè)數(shù)組，一個(gè)是比pivot小，一個(gè)是比pivot大，最后將這兩個(gè)數(shù)組和pivot進(jìn)行合并，最好情況下時(shí)間復(fù)雜度為O(n log n)，最差情況下時(shí)間復(fù)雜度為O(n2)

def quick_sort(seq):
 if len(seq) >= 1:
  pivot_idx = len(seq)//2
  small, large = [], []
  for i, val in enumerate(seq):
   if i != pivot_idx:
    if val <= seq[pivot_idx]:
     small.append(val)
    else:
     large.append(val)
  quick_sort(small)
  quick_sort(large)
  return small + [seq[pivot_idx]] + large
 else:
  return seq

歸并排序

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

# 1nd: 將兩個(gè)有序數(shù)組合并到一個(gè)數(shù)組
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:]
 return result
def merge_sort(lists):
 if len(lists) <= 1:
  return lists
 num = len(lists) / 2
 left = merge_sort(lists[:num])
 right = merge_sort(lists[num:])
 return merge(left, right)
# 2nd: use merge
from heapq import merge
def merge_sort2(m):
 if len(m) <= 1:
  return m
 middle = len(m) // 2
 left = m[:middle]
 right = m[middle:]
 left = merge_sort(left)
 right = merge_sort(right)
 return list(merge(left, right))

堆排序

原理：堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。平均時(shí)間復(fù)雜度為O(n logn)

# 1nd: normal
def swap(seq, i, j):
 seq[i], seq[j] = seq[j], seq[i]
# 調(diào)整堆
def heapify(seq, end, i):
 l = 2 * i + 1
 r = 2 * (i + 1)
 ma = i
 if l < end and seq[i] < seq[l]:
  ma = l
 if r < end and seq[ma] < seq[r]:
  ma = r
 if ma != i:
  swap(seq, i, ma)
  heapify(seq, end, ma)
def heap_sort(seq):
 end = len(seq)
 start = end // 2 - 1
 # 創(chuàng)建堆
 for i in range(start, -1, -1):
  heapify(seq, end, i)
 for i in range(end - 1, 0, -1):
  swap(seq, i, 0)
  heapify(seq, i, 0)
 return seq
# 2nd: use heapq
import heapq
def heap_sort2(seq):
 """ Implementation of heap sort """
 heapq.heapify(seq)
 return [heapq.heappop(seq) for _ in range(len(seq))]

希爾排序

原理：希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

def shell_sort(seq):
 count = len(seq)
 step = 2
 group = count // step
 while group > 0:
 for i in range(0, group):
 j = i + group
 while j < count:
 k = j - group
 key = seq[j]
 while k >= 0:
  if seq[k] > key:
  seq[k + group] = seq[k]
  seq[k] = key
  k -= group
 j += group
 group //= step
 return seq

區(qū)別