排序算法，下面算法均是使用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