python 快速排序_Python实现经典算法--快速排序

《python实现经典算法》将会是一系列文章，同时还有个配套系列同时进行，《C++实现经典算法》,源自面试的教训。

直接上代码：

def quickSort(list,p,r):
	if p<r:
		q=partion(list,p,r)
		quickSort(list,p,q-1)
		quickSort(list,q+1,r)

def partion(list,p,r):
	i=p-1
	for j in range(p,r):
		if list[j]<list[r]:
			i+=1
			list[i],list[j]=list[j],list[i]
	print('+',list,'+')
	list[i+1],list[r]=list[r],list[i+1]
	return i+1



x = input("请输入:")

list1 = x.split(',')
list1 = [int(list1[i]) for i in range(len(list1))]


quickSort(list1,0,len(list1)-1)
print(list1)
           

快速排序算法的经典性想必大家都很清楚，就不赘言，其核心思想在于分治。每次选取出一个基准值，遍历整个序列，将序列中所有小于基准值的数挪到该基准值的左边，大于基准值的放到右边，然后再分别对基准值左半部分和右半部分的列表重复同样操作，直到退出。我代码选取每次最右边的那个数作为基准值。

改良版：

def quickSort_n(a):
    if len(a) <= 1:
        return a
    pivot = a[0]
    greater = [element for element in a[1:] if element > pivot]
    lessor = [element for element in a[1:] if element <= pivot]
    return quickSort_n(greater) + [pivot] + quickSort_n(lessor)
           

最后的结果是从大到小输出。该版本更加简洁易懂，也能更加的显示python的威力