- 步骤
在一序列中定一个轴为基轴(通常为了方便定最左那个数),定序列左右指针,右指针开始扫描,比基轴大则指针继续往前扫,当扫到比基轴小时,把这个数放到最左边,再开始扫左边指针,遇到比较大的数则放到最右方,当两指针相遇时,把基轴的那位数放到这个位置上,递归执行,直至扫到左右序列长度为一时返回;
2.复杂度,平均复杂度为nlogn
3.代码
def quick_sort(lists, low, high):标签:__,right,python,list1,lists,基轴,排序,快速,left From: https://www.cnblogs.com/sardine96/p/17001750.html
if low >= high:
return
left = low
right = high
pivot = lists[left]
while left < right:
while left < right and lists[right] >= pivot:
right -= 1
if left < right:
lists[left] = lists[right]
while left < right and lists[left] <= pivot:
left += 1
if left < right:
lists[right] = lists[left]
if left >= right:
lists[left] = pivot
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
if __name__ == '__main__':
list1 = [4, 10, 22, 22, 10, 9]
quick_sort(list1, 0, len(list1) - 1)
print(list1)