Python排序算法实例代码

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