python数据结构之quick_sor

Quick sort , also known as partition-exchange sort, divides the data to be sorted into two separate parts by a single sort, in which all the data of one part is smaller than all the other parts. Then, according to this method, the two parts of the data are sorted separately, and the whole sorting process can be recursively, so that the entire data becomes an ordered sequence. The steps are: 1. Pick an element from the series, called "pivot", 2. Reorder the series, all elements are placed in front of the reference smaller than the reference value, and all elements are placed larger than the reference value. Behind the benchmark (the same number can go to either side). After the end of this partition, the benchmark is in the middle of the sequence. This is called a partition operation. 3. Recursively sorts sub-columns that are smaller than the reference value element and sub-columns that are larger than the reference value element. The bottommost case of recursion is that the size of the series is zero or one, that is, it has always been sorted. Although it has been recursively, this algorithm will always end, because in each iteration, it will at least put an element to its final position.

image

代码如下：

def quick_sort(alist,start,end):
    if start >= end:
       return

    mid = alist[start]
    #设置初始元素
    low = start
    high = end
    while low < high :
        #判断是否排序完成
        # 后面元素左移
        while low < high and alist[high] >= mid:
            high -=1
        alist[low]=alist[high]
        #后面元素左移
        # 前面元素右移
        while low < high and alist[low]< mid:
            low +=1
        alist[high]=alist[low]
    alist[low]=mid
    #分开排序
    quick_sort(alist,start,low-1)
    quick_sort(alist,low+1,end)
# 执行函数打印   
alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)