python实现快速排序
2021-02-07 21:16
标签：color print 赋值 log div 子序列 tps logs shu https://www.cnblogs.com/Hangingter/p/9589427.html https://www.jianshu.com/p/2b2f1f79984e python实现快速排序 标签：color print 赋值 log div 子序列 tps logs shu 原文地址：https://www.cnblogs.com/come202011/p/12773433.html# -*- coding: utf-8 -*-
# @Time : 2020/4/25 15:27
# @File : quick_sort.py
# @Author: Hero Liu
# 快速排序
# 一开始假定数组第一个元素是基准值
# 设定两个指针:左指针和右指针,分别指向数组的头部元素和尾部元素
# 1)然后从数组尾部往左扫描,如果元素值大于基准值,则右指针向左偏移
# 如果右指针指向的元素小于基准值,那么把这个元素值赋值给左指针
# 2)右边扫描完一次后开始从数组头部往右扫描,如果左指针指向的元素小于基准值,则左指针继续向右偏移
# 偏移后继续判断左指针指向的元素与基准值的大小,如果左指针指向的值大于基准值,那么把这个值赋值给右指针
# 3)重复上述1)、2)步骤，直到左右指针重合，此时指针左边的值即是所有小于基准值的元素
# 指针右边的值即是所有大于基准值的元素
# 4）再分别对指针左边的子序列和指针右边的子序列进行上述排序【递归】
def quick_sort(L):
return q_sort(L, 0, len(L) - 1)
def q_sort(L, left, right):
if left right:
pivot = partition(L, left, right)
q_sort(L, left, pivot - 1)
q_sort(L, pivot + 1, right)
return L
def partition(L, left, right):
pivotkey = L[left]
while left right:
while left and L[right] >= pivotkey:
right -= 1
L[left] = L[right]
while left and L[left] pivotkey:
left += 1
L[right] = L[left]
L[left] = pivotkey
return left
L = [5, 9, 1, 11, 6, 7, 2, 4]
print(quick_sort(L))