快速排序算法:如何使用Python实现快速排序?
发布时间:2023-06-21 01:50:02
快速排序(Quick Sort)是一种常用的排序算法,它基于分治的思想,通过将待排序的序列分成两个子序列,然后递归的对两个子序列进行排序,最终合并成有序的序列。在实际应用中,快速排序算法被广泛应用,其效率较高,时间复杂度为O(nlogn)。
以下是使用Python语言实现快速排序算法的示例代码:
def quick_sort(arr,left,right):
if left>=right: #如果左边索引大于等于右边索引就代表已经整理完毕一个组了
return
low=left
high=right
key=arr[low] #定义最左边的数为基准值
while left<right:
while left<right and arr[right]>=key:
right-=1
arr[left]=arr[right] #将比右边小的数放到左边
while left<right and arr[left]<=key:
left+=1
arr[right]=arr[left] #将比左边大的数放到右边
arr[right]=key #将基准值放到合适的位置
quick_sort(arr,low,left-1) #对左边进行快排
quick_sort(arr,left+1,high) #对右边进行快排
arr=[6,1,2,7,9,3,4,5,10,8]
quick_sort(arr,0,len(arr)-1)
print(arr)
代码解析:
1. 定义quick_sort函数,其中arr为待排序的列表,left为列表的 个元素的下标,right为列表的最后一个元素的下标。
2. 判断如果左边索引大于等于右边索引就代表已经整理完毕一个组了,返回None。
3. 定义low为left,high为right,key为arr[low],即将最左边的数作为基准值。
4. 在循环中,先从右往左遍历,找到 个比基准值小的数,将其赋值给arr[left],再从左往右遍历,找到 个比基准值大的数,将其赋值给arr[right]。循环直到left>=right。
5. 将 个数作为基准值的位置放入合适的位置,即将arr[right]赋值为key。
6. 对左边进行递归排序,即quick_sort(arr,low,left-1)。
7. 对右边进行递归排序,即quick_sort(arr,left+1,high)。
8. 输出最终结果,即排好序的arr。
上述代码就是使用Python语言实现快速排序算法的示例,读者可以自行在代码中测试不同的列表进行排序,以理解快速排序算法的实现过程。
