Python递归实现快速排序

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

#快速排序
def quick_sort(rank,left,right):
    """
    快速排序思想：
    先找一个基准值，比如找最左边的第一个为基准值，开始从右往左变了，如果有比基准值小的，那么就和基准值交换位置，
    交换完位置后，再从左向右遍历，如果有比基准值大的，那么和基准值交换位置，直到基准值左边的数都比基准值小，右边的数都比基准值大
    如果在遍历过程中左边的数都比基准值小，右边的数都比基准值大，那么基准值右移一位，进行递归循环。
    递归循环时，基准值分别是左边的第一个数和右边的第一个数。递归的出口是左边只剩一个数，右边只剩一个数
    :param rank: 待排序的列表
    :param left: 未排序的列表左边第一个元素
    :param right: 未排序的列表右边第一个元素
    :return:
    """
    #基准值为左边第一个
    base=rank[left]
    l=left
    h=right
    #所有值遍历完
    while l<h:
        #从右向左遍历
        while l< h:
            #如果右边有比基准值小的，交换位置
            if rank[h]<base:
                rank[h],rank[l]=rank[l],rank[h]
                #左边右移
                l+=1
                break
            else:
                #没有比基准值小的，
                h=h-1

        #从左向右遍历
        while l<h:
            #如果有比基准值大的，交换位置
            if rank[l]>base:
               rank[l],rank[h]=rank[h],rank[l]
               #右边左移
               h=h-1
               break
            else:
                l+=1
    #左边排序完成
    if l<=left:
        pass
    #如果左边排序未完成，就递归
    else:
        quick_sort(rank,left,l-1)
    #右边排序完成
    if h>=right:
        pass
    #右边排序未完成，递归
    else:
        quick_sort(rank,h+1,right)

rank=[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
quick_sort(rank,0,len(rank)-1)
print(rank)

运行结果：
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

今天的文章Python递归实现快速排序分享到此就结束了，感谢您的阅读。