快速排序（Python实现）

目录

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

1. 快速排序--while版本

def quick_sort_while(b_list, first, last):
	'''快速排序'''
	if first >= last:
		return b_list
	
	start     = first
	end      = last
	mid_value = b_list[first];

	while start < end:
		while start < end and b_list[end] >= mid_value:
			end -= 1
		b_list[start] = b_list[end]

		while start < end and b_list[start] <= mid_value:
			start += 1
		b_list[end] = b_list[start]

	b_list[start] = mid_value

	quick_sort_while(b_list, first, start-1)
	quick_sort_while(b_list, start+1, last)

2. 测试用例

if __name__ == '__main__':
	b_list = [3,4,7,9,2,1]
	quick_sort_while(b_list,0,len(b_list)-1)
	print(b_list)

3. 算法时间复杂度分析

• 最坏时间复杂度：O(n²)
• 最好时间复杂度：O(nlog₂n)
• 稳定性：不稳定