欢迎访问宙启技术站
智能推送

快速排序算法:如何使用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语言实现快速排序算法的示例,读者可以自行在代码中测试不同的列表进行排序,以理解快速排序算法的实现过程。