插入排序（Python实现）

2024-10-12 22:09:20

目录

1. for版本--插入排序
2. while版本--插入排序
3. 测试用例
4. 算法时间复杂度分析

1. for版本--插入排序

def insert_sort_for(a_list):

	'''插入排序for版本'''

	num = len(a_list)

	for j in range(1,num):

		for i in range(j,0,-1):

			if a_list[i] < a_list[i-1]:

				a_list[i-1],a_list[i] = a_list[i],a_list[i-1]

			else:

				break

	return a_list

2. while版本--插入排序

def insert_sort_while(b_list):

	'''插入排序while版本'''

	num = len(b_list)

	j=1

	while j < num:

		i = j

		while i > 0:

			if b_list[i] < b_list[i-1]:

				b_list[i-1],b_list[i] = b_list[i],b_list[i-1]

				i -= 1

			else:

				break

		j += 1

	return b_list

3. 测试用例

if __name__ == '__main__':

	a_list = [4,2,1,5,9,8]

	print(insert_sort_for(a_list))

	b_list = [4,3,9,1,5,6]

	print(insert_sort_while(b_list))

4. 算法时间复杂度分析

最好时间复杂度：O(n) (升序排列，序列已经处于升序状态了)

最坏时间复杂度：O(n²)

稳定性：稳定

最新文章

热门文章