快速排序python-3

p1_1 快速排序python-3
题目：给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

#python中没有i++，只有i+=1
#//表示向下取整
#两个符号命值可一起，就像换值一样
#循环等冒号后面可以不换行加一句话，但是不能两句话
#' '.join(map(str,nums)  这个函数只针对字符串

#快排：从长到短的变，先整体保证左右两边大小，再分别xx【百度云第八章5-24min

#记忆：扩充---先移动一个（调整之后要移动）,后调整！移动很严格，调整之前还要再判断
#复杂度为O(nlogn)，python自带的sort函数排序貌似更快【期望递归层为logn，每一层复杂度为n】

#选x
#调整，st左<=x,右>=x，和x相等的无所谓哪边！【快排不稳定，也可以通过把ai记为,则每个数都不一样，稳定【但是指针移动的前提是所指的数字=r:
        return nums#不可以少，这是迭代终止所必须的！
    x=nums[(l+r)//2]
    i, j = l-1, r+1 #要换符号成ij是因为子列也要这个函数。  i,j初始值是对列表的左右扩充，因为后面先移动再比较！
    while i=x: break #这里一定要加等号，遇到相等的点也要交换！【若出现i=j=x的时候，这会导致直接i=j+2，这不对
        while True:
            j-=1
            if nums[j]<=x: break
        if ij的情况，此时就不能交换值了，这说明已调整好了！若出现i=j肯定=x也不用交换了
    #一次迭代结束，排序over的原因：若i=j，则指向相同的数，结束迭代这个数=x，所以以i/j做划分都行   【i=j=x】
    #若i>j,则j，i的顺序，    j在i左边，所以j的数x                             【ji即小大】
    #对每一子表进行迭代
    quick_sort(nums,l,j)#对左子表迭代，不需要分割num作为参数，因为有指针
    quick_sort(nums,j+1,r)#若是i>j的情况，这里第二个参数可以写i=j+1，但是若i=j就不能写i了，只能j+1，所以最终j+1

main()