python排序算法问题总结

1、 选择排序

代码

for i in range(len(l)):
    min_index=i
    for j in range(i+1,len(l)):
        if l[min_index]>l[j]:
            min_index=j
    l[i],l[min_index]=l[min_index],l[i]

算法思路

• 遍历列表A，假定最小值下标为0，找到最小值下标min_index，最后A[min_index]跟A[0]值位置调换
• 遍历列表A[1:]，假定最小值下标为1，找到最小值下标min_index，最后A[min_index]跟A[1]值位置调换，以此类推。。。

算法复杂度

• 时间复杂度：(N+N-1+N+N-2...+1)*(看、比、更)+N——>aN²+bN+C——>O(N²)
• 额外空间复杂度：O(3)

2、冒泡排序

代码

for i in range(len(l)):
    for j in range(i+1,len(l)):
        if l[i]>l[j]:
            l[i],l[j]=l[j],l[i]

算法思路

• 遍历列表A，如果A[1]<A[0]，A[0]和A[1]交换位置，否则位置不变，遍历结束找到A[0]等于最小值
• 遍历列表A[1:]，交换后A[1]等于次小值，以此类推。。。

算法复杂度

• 时间复杂度：(N+N-1+N+N-2...+1)*(看、比、更)——>aN²+bN+C——>O(N²)
• 额外空间复杂度：O(2)

3、插入排序

代码

for i in range(len(l)):
    j=i
    while j-1>=0:
        if l[j-1]>l[j]:
            l[j-1],l[j]=l[j],l[j-1]
        j-=1

算法思路

• 遍历列表A，如果A[0]>A[1]，A[0]和A[1]交换位置，否则位置不变,结束循环
• 遍历列表A，如果A[1]>A[2]，A[1]和A[2]交换位置，如果A[0]>A[1]，A[0]和A[1]交换位置，否则位置不变,结束内层循环,以此类推。。。

算法复杂度

• 时间复杂度(完全逆序的情况)：O(N²)
• 额外空间复杂度：O(2)

4、快速排序

# 基础模型
def quick_sort(l:list):
    if len(l)<=1:# 递归边界，就是递归树最末端
        return l
    base=l[0]
    left,mid,right=[],[],[] 
    for i in l:
        if i<base:
            left.append(i)
        elif i>base:
            right.append(i)
        else:
            mid.append(i)
    return quick_sort(left)+mid +quick_sort(right) #递归排序两端
# 优化防止最糟糕情况
def quick_sort(l:list):
    if len(l)<=1:
        return l
    left,mid,right=[],[],[]
    base_index=random.randint(0,len(l)-1) # 随机选取分组对象，可以最大限度使得当前排序的时间复杂度接近O(nlogn)
    base=l[base_index]
    for i in l:
        if i<base:
            left.append(i)
        elif i>base:
            right.append(i)
        else:
            mid.append(i)
    return quick_sort(left)+mid+quick_sort(right)
quick_sort(l)

pythonic快排表达式：
quick_sort= lambda l:l if len(l)<=1 else quick_sort([i for i in l[1:] if i<=l[0]])+[l[0]]+quick_sort([j for j in l[1:] if j>l[0]])

参考

https://www.cnblogs.com/pythonbao/p/10768593.html

算法复杂度

时间复杂度：快排的时间复杂度为O(nlogn)
空间复杂度：排序时需要另外申请空间，并且随着数列规模增大而增大，其复杂度为：O(nlogn)