Python排序算法實例代碼

2019-11-25 15:57:03

字體：大中小

來源：轉載

供稿：網友

排序算法，下面算法均是使用Python實現：

插入排序

原理：循環一次就移動一次元素到數組中正確的位置，通常使用在長度較小的數組的情況以及作為其它復雜排序算法的一部分，比如mergesort或quicksort。時間復雜度為 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: 加速版本，利用已經排好了序的進行二分查找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: 原理同上，使用bisectimport bisectdef insertion_sort4(seq): for i in range(1, len(seq)):  bisect.insort(seq, seq.pop(i), 0, i) # 默認插在相同元素的左邊 return seq

選擇排序

原理：每一趟都選擇最小的值和當前下標的值進行交換，適用在大型的數組，時間復雜度為 O(n2)

# 1nd: fordef 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: mindef 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

冒泡排序

原理：比較數組中兩兩相鄰的數，如果第一個大于第二個，就進行交換，重復地走訪過要排序的數列，達到將最小的值移動到最上面的目的，適用于小型數組，時間復雜度為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 seqdef 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

快速排序

原理：從數組中選擇pivot，分成兩個數組，一個是比pivot小，一個是比pivot大，最后將這兩個數組和pivot進行合并，最好情況下時間復雜度為O(n log n)，最差情況下時間復雜度為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）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

# 1nd: 將兩個有序數組合并到一個數組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 resultdef 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 mergefrom heapq import mergedef 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)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大于其父節點的值，即A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。平均時間復雜度為O(n logn)

# 1nd: normaldef swap(seq, i, j): seq[i], seq[j] = seq[j], seq[i]# 調整堆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 # 創建堆 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 heapqimport heapqdef heap_sort2(seq): """ Implementation of heap sort """ heapq.heapify(seq) return [heapq.heappop(seq) for _ in range(len(seq))]

希爾排序

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

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

區別