python五大基本算法之快速排序

快速排序的思想：首先选取一个基准数（一般为第一个数），然后将比它小得数放到左边，比它大的数放到右边，这一个过程称为一趟快速排序。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
快速排序分析：
python五大基本算法之快速排序
代码块：

#快速排序
def func(my_list,start,end):

    #建立终止条件
    if start >= end:
        return

    #x为左边向右移动的游标
    #y为右边向右移动的游标
    x,y = start,end

    #建立基准元素
    base = my_list[start]

    while x < y:

        #当x<y,并且对应的元素都大于基准元素，游标向左移动
        while x < y and my_list[y] >= base:
            y = y - 1

        #如果小于基准元素，则将值赋给x游标对应的元素
        my_list[x] = my_list[y]

        #当x<y,并且对应的元素都小于基准元素，游标向右移动
        while x < y and my_list[x] <= base:
            x = x + 1

        #如果大于基准元素，则将值赋给y游标对应的元素
        my_list[y] = my_list[x]

    #当循环结束之后，x=y，则将基准元素赋值给x游标对应的元素
    my_list[x] = base

    #此时序列被分成了前后两部分，利用递归调用继续排序
    #前半部分序列进行递归
    func(my_list,start,y-1)

    #后半部分序列进行递归
    func(my_list,y+1,end)
    return my_list

if __name__ == '__main__':
    my_list = [45, 62, 23, 12, 54, 78, 96, 31]
    func(my_list, 0, len(my_list) - 1)
    print(my_list)

运行之后的结果为：

[12, 23, 31, 45, 54, 62, 78, 96]

python五大基本算法之快速排序

相关推荐