排序算法有很多，目前最好的是quick_sort:unstable，spatial complexity is nlogN.
快速排序原理
python实现
严蔚敏的 datastruct书中有伪代码实现，因为Amazon面试需要排序，所以用python实现了。
两种实现方法，功能一致，效率没测，请高手留言
第一种实现
标准算法，严蔚敏书中的伪代码实现
#!/usr/bin/python
# -*- coding: utf-8 -*-
'''
@author: willard
'''
def quick_sort_standord(array,low,high):
''' realize from book "data struct" of author 严蔚敏
'''
if low < high:
key_index = partion(array,low,high)
quick_sort_standord(array,low,key_index)
quick_sort_standord(array,key_index+1,high)
def partion(array,low,high):
key = array[low]
while low < high:
while low < high and array[high] >= key:
high -= 1
if low < high:
array[low] = array[high]
while low < high and array[low] < key:
low += 1
if low < high:
array[high] = array[low]
array[low] = key
return low
if __name__ == '__main__':
array2 = [9,3,2,1,4,6,7,0,5]
print array2
quick_sort_standord(array2,0,len(array2)-1)
print array2
第二种实现
这是特殊实现，
#!/usr/bin/python
# -*- coding: utf-8 -*-
'''
@author: willard
'''
def sub_sort(array,low,high):
key = array[low]
while low < high:
while low < high and array[high] >= key:
high -= 1
while low < high and array[high] < key:
array[low] = array[high]
low += 1
array[high] = array[low]
array[low] = key
return low
def quick_sort1(array,low,high):
if low < high:
key_index = sub_sort(array,low,high)
quick_sort1(array,low,key_index)
quick_sort1(array,key_index+1,high)
if __name__ == '__main__':
#array = [8,10,9,6,4,16,5,13,26,18,2,45,34,23,1,7,3]
array1 = [7,3,5,6,2,4,1]
print array1
quick_sort1(array1,0,len(array1)-1)
print array1