# 在python中以最后一个元素为轴实现QuickSort

``````def quicksort(array):
if len(array) >1:
print "enter array", array
pivot = len(array) - 1
print "pivot", array[pivot]
x = 0
while x < pivot:
if array[x]>array[pivot]:
piv = array[pivot]
xval = array[x]
array[x] = array[pivot-1]
array[pivot] = xval
array[pivot-1] = piv
#        temp = array[x]
#       array[x] = array[pivot]
#       array[pivot] = temp
# array.append(array.pop(x))
pivot -= 1
else:
x += 1
print "pre recur split array", array
print "left", array[:pivot]
print "right", array[pivot+1:]
quicksort(array[:pivot])
quicksort(array[pivot+1:])
print "post recur split array", array
return array
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
#test = [21, 4, 1, 3]
print quicksort(test)
``````

``````    quicksort(array[:pivot])
quicksort(array[pivot+1:])
``````

``````    array[:pivot] = quicksort(array[:pivot])
array[pivot+1:] = quicksort(array[pivot+1:])
``````

``````def quicksort(array):
if len(array) <= 1:
return array
pivot_val = array[-1]
lower = [x for x in array if x < pivot_val]
upper = [x for x in array if x > pivot_val]
pivot_count = array.count(pivot)
return quicksort(lower) + [pivot_val]*pivot_count + quicksort(upper)
``````

``````def quicksort(array, low=0, high=None):    # add optional arguments
if high == None:
high = len(array) - 1              # set high if it got the default
if high - low > 0:
pivot = high                       # use high and low to set up pivot and x
x = low
while x < pivot:
if array[x]>array[pivot]:      # this part stays the same
piv = array[pivot]
xval = array[x]
array[x] = array[pivot-1]
array[pivot] = xval
array[pivot-1] = piv
pivot -= 1
else:
x += 1
quicksort(array, low, pivot-1)     # pass on new high and low values
quicksort(array, pivot+1, high)
return array                           # you probably don't need this line any more
``````

0 条评论