归并排序（Python实现）

1. 归并排序--while版本
2. 测试用例
3. 算法时间复杂度分析

1. 归并排序--while版本

def merge_sort_while(b_list):

	'''归并排序--while版本'''

	num = len(b_list)

	if num <= 1:

		return b_list

	middle = num // 2

	# left 采用归并排序后形成的有序的新列表

	left_list  = merge_sort_while(b_list[:middle])

	# right 采用归并排序后形成的有序的新列表

	right_list = merge_sort_while(b_list[middle:])

	right_pointer = left_pointer = 0

	res = []

	# 将连个有序的子列表合并为一个新的列表

	while left_pointer < len(left_list) and right_pointer < len(right_list):

		if right_list[right_pointer] < left_list[left_pointer]:

			res.append(right_list[right_pointer])

			right_pointer += 1

		else:

			res.append(left_list[left_pointer])

			left_pointer += 1

	res += left_list[left_pointer:]

	res += right_list[right_pointer:]

	return res

2. 测试用例

if __name__ == '__main__':

	b_list = [3,2,1,8,7,5]

	print(merge_sort_while(b_list))

3. 算法时间复杂度分析

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

最好时间复杂度：O(nlog₂n)

稳定性：稳定

巴特西

归并排序（Python实现）

1. 归并排序--while版本

2. 测试用例

3. 算法时间复杂度分析

最新文章

热门文章