'''

目标:实现快速排序

概念:
	从列表中任意选一个元素作为基准
	然后将所有比基准小的数都放到它的左边
	将所有比基准大的数都放到它的右边
	对左边和右边的元素集不断重复上面的操作
	直到排序完成
'''
import random

def qsort(List):
	if len(List)>=2:
		base = random.choice(List)
		left_base = []
		right_base = []
		equal = []
		for num in range(len(List)):
			if List[num]<base:
				left_base.append(List[num])
			elif List[num]>base:
				right_base.append(List[num])
			else:
				equal.append(List[num])

		return qsort(left_base)+equal+qsort(right_base)
	else:
		return List

if __name__ == '__main__':

	List = [[2],[2,6,3,7,9,1,5],[2,2,6,6,3,8,1,9]]
	for i in List:
		try:
			result = qsort(i)
			print(result)
			print("排序成功\n")
		except:
			print("排序失败")