[Python知识库]快速排序-python3实现

快速排序算法-python实现

# lst-传入列表，i-左边界，j-右边界
def quick_sort(lst, i, j):
	# 越界退出
	if i >= j:
		return
	# 选取lst最左侧元素为pivot，将左右边界赋值给low、high指针
	pivot = lst[i]
	low = i
	high = j
	while low < high:
		# 从后往前找一个比pivot小的元素
		while low < high and lst[high] >= pivot:
			high -= 1
		lst[low] = lst[high]
		# 从前往后找一个比pivot大的元素
		while low < high and lst[low] <= pivot:
			low += 1
		lst[high] = lst[low]
	# 循环结束后，low即为列表中位index，将pivot值放在列表中间
	lst[low] = pivot
	# 分别在pivot左右进行快排
	quick_sort(lst, i, low - 1)
	quick_sort(lst, low + 1, j)
	return lst