● 基础 ● 编码简单,易于实现,是一些简单情景的首选 ● 在一些特殊情况下,简单的排序算法更有效 ● 简单的排序算法思想衍生出复杂的排序算法 ● 作为子过程,改进更复杂的排序算法
每次选择没有排序部分的最小值和第一位交换
def selection_sort(org_arr, length):
"""
选择排序,每次选择未排序部分的最小值和未排序部分的第一位交换位置
:param org_arr: 待排序数组
:param length: 待数组长度
:return:
"""
for i in range(0, length):
# 寻找[i,n)区间里的最小值
main_index = i
for j in range(i+1, length):
if org_arr[j] < org_arr[main_index]:
main_index = j
org_arr[i], org_arr[main_index] = org_arr[main_index], org_arr[i]
从左到右遍历每一个元素,每次将这个元素和前面的元素一一比较,如果比某个元素小,则跟其交换
def insert_sort(arr, n):
"""
选择排序,每次选择未排序部分的最小值和未排序部分的第一位交换位置
:param arr:
:param n:
"""
for i in range(0, n):
# 寻找元素arr[i]合适的插入位置
e = arr[i]
j = i # j保存元素e应该插入的位置
while arr[j-1] > e and j > 0:
arr[j] = arr[j-1]
j -= 1
arr[j] = e
arr[j-1] > e
),可以提前终止内层循环这使得在一个近乎有序的数组在进行插入排序的时候,效率要高的多,设置比o(logn)的算法效率还要高 当排序一个完全排序的数组时,插入排序的算法复杂度为o(n)级别