插入排序InsertionSort

发表于 | 分类于 | 阅读次数 ℃
本文字数： 313 | 阅读时长 ≈ 1 分钟

插入排序是一种基于比较的排序算法，将整个数据集分为已排区间和未排区间，从未排区间中取出首个元素，按逆序方式遍历已排区间，将其插入到合适位置

1
2
3
4
5
6
7
8
9
def InsertionSort(arr):
	length = len(arr)
	for i in range(1, length):
		val = arr[i]
		j = i - 1
		while j >= 0 and arr[j] > value: # 也可以用其他循环方式，不过while是最简洁的形式
			arr[j+1] = arr[j]
			j -= 1
		arr[j+1] = val # 为什么还是要赋值给j+1呢？因为while循环已经提前-1操作了！