# 

python

python

# 

C.R.A.Hoare1962(Divide-and-ConquerMethod)

1 



2

R[low..high]

### 

R[low..high](Pivot)R[low..pivotpos-1)R[pivotpos+1..high](pivot)pivot.keypivot.keypivot(pivotpos)



pivotpos(pivot=R[pivotpos])

R[low..pivotpos-1].keysR[pivotpos].keyR[pivotpos+1..high].keys

lowpivotposhigh

### 

R[low..pivotpos-1]R[pivotpos+1..high]

### 

""""

### (Python)
	
```python
	#!/usr/bin/env python
	#coding:utf-8
	
	#1
	
	def quickSort(arr):
	    less = []
	    pivotList = []
	    more = []
	    if len(arr)  pivot:
	                more.append(i)
	            else:
	                pivotList.append(i)
	
	        less = quickSort(less)      #
	        more = quickSort(more)
	
	        return less + pivotList + more
	
	# 2
	# , = 
	# 1000100=1801, = 201
	def qsort(L):
	    return (qsort([y for y in L[1:] if y <  L[0]]) + L[:1] + [y for y in L[1:] if y == L[0] + qsort([y for y in L[1:] if y > L[0]])) if len(L) > 1 else L
	
	#3
	#
	
	def qsort(list):
	    if not list:
	        return []
	    else:
	        pivot = list[0]
	        less = [x for x in list     if x <  pivot]
	        more = [x for x in list[1:] if x >= pivot]
	        return qsort(less) + [pivot] + qsort(more)
	
	#4
	
	from random import *
	
	def qSort(a):
	    if len(a)  q])
	
	
	#5
	#
	
	qs = lambda xs : ( (len(xs) = xs[0]] ) ] )[0]
	
	
	if __name__=="__main__":
	    a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
	    print quickSort(a)
	    print qSort(a)
	
	    print qs(a)
```