Python纯代码实现快速排序算法
Python实现快速排序算法
代码
'''
排序的数据只能是列表，但是列表中元素的数据可以是其他类型的，因为有⾃定义函数进⾏⽐较；
排序的范围是给定的下表[p, r]间的的元素，包括p和r；
返回值是r下标的数据在列表下标[p, r]对应的数据中正确的排序位置；
在计算下标r的数据的位置时，还进⾏数据的排序，排序会按照给定的函数进⾏数据的⽐较；
函数的返回值是true则是升序排序，否则是降序排序（升序降序只是对有序列表的⼀个描述）。
按实际的数据类型进⾏函数的编写。
'''
# 经典分区思路的另⼀种
def partion(list, low, height, fun):
i, j = low, low
while j < height:# 此处使⽤for循环需要使⽤range函数⽣成列表，会造成资源浪费和效率的降低，所以使⽤while是理想的选择
if fun(list[j],list[height]):
list[i],list[j]=list[j],list[i]
i +=1
j +=1
list[i],list[height]=list[height],list[i]
return i
# 经典分区思路快速排序python实现
def partion1(list, low, height):
temp =list[low]
while low < height:
while low < height and list[height]> temp:
height -=1
list[low]=list[height]
while low < height and list[low]<= temp:
low +=1
list[height]=list[low]
list[low]= temp
return low
# 快速排序
def quickSort(list, p, r, fun):
if p < r:
q = partion(list, p, r, fun)# 返回值是列表中最后⼀个元素的正确位置
quickSort(list, p, q -1, fun)# 排序正确位置下标前部分
quickSort(list, q +1, r, fun)# 排序正确位置下标后部分
if __name__ =="__main__":
# 快速排序排序⽅式函数
# 如果将 a < b 改成 a > b 则降序排序
def func(a, b):
if a < b:
return True
list1=[15,2,8,7,1,3,5,60,95,3,56,34,123,4213,12,341,5,123,4,12,61,234,15,324,123,12,3,21,4,23,41,5,2134,32,5,123,4,2315,123,5123,5,21,5]    quickSort(list1,0,len(list1)-1, func)
print(list1)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。