快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n个项目要 O(nlog n)（大O符号）次比较。在最坏状况下则需要 O(n^{2})} {O(n^{2})次比较，但这种状况并不常见。事实上，快速排序 Theta (nlog n)通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
从数列中挑出一个元素，称为“基准”（pivot），
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

本例采用原地排序版本。
简单版本的缺点是，它需要 Omega (n)的额外存储空间，也就跟归并排序一样不好。额外需要的存储器空间配置，在实际上的实现，也会极度影响速度和缓存的性能。有一个比较复杂使用原地（in-place）分割算法的版本，且在好的基准选择上，平均可以达到 O(log n)空间的使用复杂度。

#quick sort
class QuickSort:	
	def main(self,c):
		assert type(c) == list or type(c) == tuple
		list1 = list(c)
		n = len(list1)
		self.sort(list1,0,n)
		return type(c)(list1)

	def sort(self,c,left,right):
#		print("C:",c,"L:",left ,"R:",right)		
		n = len(c)
		if n < 2:
			return c
		if right - left < 2:
			return c
		de = self.quicksort(c,left,right-1)
		self.sort(c,left,de)
		self.sort(c,de+1,right)
		return c
	
	def quicksort(self,c,s,p):
		r = p - 1
		l = s
		pivot = c[p]
	#	print("PIVOT:",pivot)
		for i in range(s,p):
			if c[i] >= pivot:
				l = i
				for j in range(r, s-1,-1):
					if l == j:
						
						c[l],c[p] = c[p],c[l]
	#					print(c)
						return l
					if c[j] <= pivot:
						r = j
						c[l],c[r] = c[r],c[l]
	#					print(c)
						break						
						
		for j in range(r, s-1,-1):
			if c[j] <= pivot:				
				c[l],c[j] = c[j],c[l]
				return j
		return p

#test
a = (9, 8, 6, 7, 4, 5, 3, 2, 1)
p = QuickSort()
print(p.main(a))