蓝桥杯算法之基础知识（7）---排序题的快排和归并排序

一、快排

》快排方法，就三步

1.随便选一个值作为基准值x

2.拿选中的这个x值划分队列为左右两个区间（左边的都小于x，右边的都大于x）

3.然后递归左区间和右区间就行

》代码举例：

#qs排序

#1 6 7 8 6 5 4
#先找比较点，再划分区间，再递归---递归注意递归终止条件
#关键划分区间：一开始l,r都在边界外，然后q[i]<x i++;q[j]>x j--;
#易错点：1.将x赋值为索引，而不是具体的值---导致在使用的过程中，索引对应的值一直在变化
#2.忘记i,j的赋值
#3.递归调用的时候，选择应该是l,j和j+1到r,因为注意会有j<r的情况发生，如果选择是l,i和i+1,r
#就会对应重复的比如2，2，那么就会不断的满足递归，进而不断的使用递归，无法终止

n=1e5+10


def qs(l,r,q):
    if l>=r:
        return
   
    x=q[(l+r)//2]
    i=l-1
    j=r+1
    
    while i<j:
        i+=1
        while q[i]<x:
            i+=1
        j-=1
        while q[j]>x:
            j-=1
        
        if i<j:
            q[i],q[j]=q[j],q[i]
    qs(l,i,q)
    qs(i+1,r,q)




n=int(input())
q=[0]
q.extend(list(map(int,input().split())))
qs(1,n,q)
for i in range(1,n+1):
    print(q[i],end=" ")

或者看图片比较清晰：

二、归并排序

》归并方法，也是三步

1.首先同样是排序的套路 确定分界点

2.递归左半边 、右半边

3合并（这个合并其实就是设计一个k，去存放当前merge的左边和右边的合并【同时排序】结果）

//合并这一步，队列k，是由原队列依次从L和mid+1开始，依次右移比较最小的，就放到k里面，最后得到的k队列这就是合并的结果

》代码举例：

#先选中值，然后左右递归，然后合并
#关键点：合并，使用另外一个数组去存最终的结果，并赋值给（更新）原数组---这一步很容易忘记
#易错点：1像排序这种问题，一般都要写个终止条件
#2像排序这种问题，最忌直接将传入的参数l,r直接进行操作，而是将其分别赋给i,j，万一
#后面你要操作也是对i,j进行操作，而不是对传入的参数l,r进行操作，防止影响后面的递归等等
#3.推荐以后左边的字母换成L,因为小写的l和1不好区分
#4注意对于归并来说要将最后的另外一个数组去赋给原数组，即不断的更新原数组，进而使得
#在递归的时候，是已经排好序的数组，而不是仍为乱序的q
#5同时注意在给将k给q数组赋值的时候，q的起始值是要从L开始，而不是从1开始，因为根据递归传入的
#参数不同，L是时刻在变化的

N=1e5+10


def merge(l,r,q):
    if l>=r:
        return
    mid=(l+r)//2
    merge(l,mid,q)
    merge(mid+1,r,q)
    
    i=l
    j=mid+1
    k=[0]
    if i<j:
        while i<=mid and j<=r:
            if q[i]<q[j]:
                k.append(q[i])
                i+=1
            else:
                k.append(q[j])
                j+=1
        while i<=mid:
            k.append(q[i])
            i+=1
        while j<=r:
            k.append(q[j])
            j+=1
    for i in range(l,r+1):
        q[i]=k[i-l+1]



n=int(input())
m=[0]
m.extend(list(map(int,input().split())))
#print(m)
merge(1,n,m)
for i in range(1,n+1):
    print(m[i],end=" ")

》当然也可以看这个图片更舒服一点