快速排序特点 ：快
思路：
1.取第一个元素p,使元素p归位;
2.列表被p分成两部分,左边都比p小,右边都比p大;
3.递归完成排序.
快速排序的效率:O(nlogn)
代码实现：
def partition(li,left,right): tmp=li[left] while left<right: while left<right and li[right]>=tmp: #从右边找比tmp小的数 right-=1 # 往左走一步 li[left]=li[right] # 把右边的值写到左边空位上 此时开始找右边要填的值 while left<right and li[left]<=tmp: left+=1 # 往右走一步 li[right]=li[left] # 把左边的值写到右边空位上 li[left]=tmp # 把tmp归位 return right def quick_sort(data,left,right): if left<right: # 最少有两个元素 mid = partition(data,left,right) quick_sort(data,left,mid-1) quick_sort(data,mid+1,right) return data li=[1,5,6,7,8,9,4,2,3] print(quick_sort(li,0,len(li)-1))
总结：
该算法通过选择一个基准元素，并根据它将列表分成两个子列表来对列表进行排序，子列表根据它们是否小于或大于基准元素进行划分。然后递归地对子列表进行排序。partition 函数用于根据基准元素对列表进行分区，quick_sort 函数递归地对子列表进行排序。最后，返回排序后的列表。
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)