简单易懂的快速排序

快速排序法

基于：分治法，如同归并排序，在归并的基础上增加了一个排序的功能（根据中值把序列分为两半），并在子序列中进行分而治之，也可以用二叉递归树来模拟，
主要思想：使用一个简单的递归方法将序列 S 排序，通过分治法把S分解为子序列，递归于每一个子序列进行快速排序，然后合并这些子序列
主要分为3个步骤：分解，递归，合并

一）分解

从S中选择一个特点的元素x，作为序列的中值，将S中的所有元素分解为

left_mark 储存所有小于中值x的元素
equal_mark 储存所有等于中值x的元素
right_mark储存所有大于中值x的元素如果
equal_mark只有一个元素就是-基准值自己x
如果对中值不想有额外的开销，可以选取S序列只能的第一或者最后一个进行利用

如下代码


def partition(alist,first,last):
	'''选取中值点'''
	pivotvalue = alist[first]        #中值

	leftmark = first+1   #左有初始值
	rightmark = last
	print('中值，左右初始值',pivotvalue,leftmark,rightmark)

	done = False
	while not done:

		while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
			#左标向右移动，当中值小于数据项时，停止
			leftmark = leftmark + 1

		while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
			# 右标向左移动，当中值大于数据项时，停止
			rightmark = rightmark -1

		if rightmark < leftmark:
			'''两值交错就结束移动'''
			done = True
		else:
			#左右值交换
			temp = alist[leftmark]
			alist[leftmark] = alist[rightmark]
			alist[rightmark] = temp

二) 解决子问题：递归排序left_mark序列和right_mark序列


def quickSort(alist,first,last):
	if first<last:   #基本结束条件

		splitpoint = partition(alist,first,last)  #分裂
		print('splitpoint:',splitpoint)
		print('alist:',alist)
		quickSort(alist,first,splitpoint-1) #函数内部通过把列表进行了分裂处理
		print('left:',alist,splitpoint)
		quickSort(alist,splitpoint+1,last) #
		print('right:',alist,splitpoint)

三）合并子序列

完整代码：


def quickSort(alist,first,last):
	if first<last:   #基本结束条件

		splitpoint = partition(alist,first,last)  #分裂
		print('splitpoint:',splitpoint)
		print('alist:',alist)
		quickSort(alist,first,splitpoint-1)
		print('left:',alist,splitpoint)
		quickSort(alist,splitpoint+1,last)
		print('right:',alist,splitpoint)


def partition(alist,first,last):
	'''选取中值点'''
	pivotvalue = alist[first]        #中值

	leftmark = first+1   #左有初始值
	rightmark = last
	print('中值，左右初始值',pivotvalue,leftmark,rightmark)

	done = False
	while not done:

		while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
			#左标向右移动，当中值小于数据项时，停止
			leftmark = leftmark + 1

		while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
			# 右标向左移动，当中值大于数据项时，停止
			rightmark = rightmark -1

		if rightmark < leftmark:
			'''两值交错就结束移动'''
			done = True
		else:
			#左右值交换
			temp = alist[leftmark]
			alist[leftmark] = alist[rightmark]
			alist[rightmark] = temp
	#中值处理
	temp = alist[first]
	print('temp:',temp)
	alist[first] = alist[rightmark]  
	print('alist[first]:',alist[first])
	alist[rightmark] = temp
	print('alist[rightmark]:',alist[rightmark])


	return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist,0,len(alist)-1)
print(alist)