快速排序
# 获取基准值的最终索引位置
def
getIndex(arr
,low
,high
):
# 使用第一个元素作为基准值
key
= arr
[low
]
while low
< high
: # 当数组长度不为空时
# 从尾部开始与基准值进行比较
while low
< high and key
<= arr
[high
]:
# 元素值比基准值大，不需要进行移动
high
= high
- 1
# 元素值比基准值小，移动到头部
arr
[low
] = arr
[high
]
# 转换比较的方向，从头部开始取值
while low
< high and arr
[low
] <= key
:
# 头部元素比基准值小，不做移动
low
= low
+ 1
# 头部元素比基准值大，移动到后面
arr
[high
] = arr
[low
]
# 当low和high重合的时候，low的位置就是基准值的最终位置
arr
[low
] = key
return low # 返回low的索引位置
# 使用递归方法进行快速排序
def
quickSort(arr
,low
,high
):
if low
< high
:
key
= getIndex(arr
,low
,high
)
quickSort(arr
,low
,key
-1)
quickSort(arr
,key
+1,high
)
if __name__
== '__main__':
a
= [1,5,4,7,8,2,6,5,4,1,256,78,414,12,36]
quickSort(a
,0,len(a
)-1)
print(a
)
"""
在来亿遍
"""
def
getIndex(arr
,low
,high
):
# 首先把基准拿到
key
= arr
[high
]
# 使用i来记录头部索引
i
= low
- 1
# 开始遍历数组
for j
in range(low
,high
):
# 如果遍历元素比基准值小，移动到头部
if arr
[j
] <= key
:
i
= i
+ 1
arr
[i
],arr
[j
] = arr
[j
],arr
[i
]
# 如果遍历元素比基准值大，则位置不变
# 最后i
+1的索引位置就是基准值的最终位置
arr
[i
+1],arr
[high
] = arr
[high
],arr
[i
+1]
return i
+1
def
quickSort(arr
,low
,high
):
if low
< high
:
key
= getIndex(arr
,low
,high
)
quickSort(arr
,low
,key
-1)
quickSort(arr
,key
+1,high
)
if __name__
== '__main__':
a
= [3, 6, 8, 19, 1, 5]
quickSort(a
,0,len(a
)-1)
print(a
)
