Python排序算法实例代码排序算法实例代码
主要为大家详细介绍了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: 原理同上,使用bisect
import bisect
def insertion_sort4(seq):
for i in range(1, len(seq)):
bisect.insort(seq, seq.pop(i), 0, i) # 默认插在相同元素的左边
return seq
选择排序选择排序
原理:每一趟都选择最小的值和当前下标的值进行交换,适用在大型的数组,时间复杂度为 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
冒泡排序冒泡排序
原理:比较数组中两两相邻的数,如果第一个大于第二个,就进行交换,重复地走访过要排序的数列,达到将最小的值移动到