线性排序算法（1）
线性排序算法（1）
birdskyws
发布于 2018-09-12 15:47:51
发布于 2018-09-12 15:47:51
排序
选择排序（适用于线性排序）
思路，2层遍历
- 第一步：选择最小的元素，与第一个元素交换。
- 第二步：从第二个元素到最后一个元素，选择最小元素，与第二元素交换
- 完成前两步，第1第2元素已经排好序。继续遍历。
算法复杂度 O(n^2)
def SelectionSort(a):
for i in range(len(a)):
tmp_min = a[i]
index = i
for j in range(i,len(a)):
if a[j]<tmp_min:
index = j
tmp_min = a[j]
tmp = a[i]
a[i] = a[index]
a[index] = tmp插入排序（适用于线性排序）
思路，2层遍历
- 第一步：第二元素向前遍历，如果第一个元素比自己大，与第一个元素交换位置
- 第二步：从第三个元素到最后一个元素，向前遍历，如果前一个元素比自己大，就交换位置；
- 遍历过程中，如果发现前一个元素比自己小，结束遍历。
由于在遍历过程中，当出现前一个元素小于当前元素，提前结束比对，比选择排序算法的比对次数少。
算法复杂度 O(n^2)
def swap(a,i,j):
tmp = a[i]
a[i] = a[j]
a[j] = tmp
def InsertionSort(a):
for i in range(1,len(a)):
for j in range(i,0,-1):
if(a[j-1]>a[j]):
swap(a,j-1,j)
else:
break用赋值替换swap，对InsertionSort优化
def InsertionSortCopy(a):
for i in range(1,len(a)):
for j in range(i,0,-1):
tmp = a[j]
if(a[j-1]>tmp):
a[j] = a[j-1]
else:
a[j] = tmp本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.07.09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录