快速排序quick_sort(python的两种实现方式)

排序算法有很多,目前最好的是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
上一篇:BZOJ 1007: [HNOI2008]水平可见直线 栈/计算几何


下一篇:BZOJ 1007: [HNOI2008]水平可见直线 平面直线