【算法之Python篇】基础排序

【算法之Python篇】基础排序 冒泡排序

冒泡排序是排序算法中信手拈来的算法之一，我们也知道时间复杂度渐进上界O(n^2)
时间复杂度渐进下届O(n)，话不多说写个代码出来我们一起研究。

def pp_sort(num):
    for i in range(len(num),0,-1):
        for j in range(i-1):
            if num[j]>num[j+1]:
                num[j],num[j+1]=num[j+1],num[j]
    return num 
            

emmm平平无奇，那么我们现在上一个优化版冒泡排序。

def vpp_sort(num):
    flag=0
    for i in range(len(num),0,-1):
        for j in range(i-1):
            if num[j]>num[j+1]:
                num[j],num[j+1]=num[j+1],num[j]
                flag=1
        if flag==0:
            break
        else:
            flag=0
    return num

从代码上看只是多个flag变量，它是用来标记排序过程中是否有交换的痕迹，如果本次冒泡遍历存在交换，那就继续进行它应该的程序。但是此次遍历没有进行交换，那么就说明此时要排序的序列已经排序好了，我们就可以大胆的结束掉循环遍历，进行返回了。
我们通过打印出i和j当前处于状态就可以清晰的看出来。待排序列[9,5,4,10,2,2]

优化前 ↓

优化后

可以清楚的看出少了一次循环，如果还是不太清晰，我们换个例子，待排序列[1,2,3,5,4,6,7]
优化前

优化后

嚯！这样就清晰的看出如果，待排序列是部分有序时，我们使用普通的冒泡排序就会浪费多余的时间去进行遍历，但是使用了优化版的冒泡排序，就会省掉许多不需要浪费时间，但与此同时也会浪费相应的空间。正所谓是有利也有弊吧！

插入排序

以这个待排序列[9,5,4,10,2,2]为例，插入排序则分为一个有序序列和一个无序序列，有序序列是通过插入排序排好的序列，无序序列是待排序列。第一个数加到有序序列中，毋庸置疑就是有序的。接下来我们说说遍历到第二个数时也就是5这个数与前一个数9进行比较时，很明显要放在9前面，这时插入排序算法就体现在这了，此时需要将5进行存储并进行pop()出栈，在实行insert()插入 *** 作即可完成本次排序。等到所有数都遍历完返回。
注：有序序列在插入新的元素后怎么保持有序？解决办法就是在遍历一次有序序列。
时间复杂度渐进上界O(n^2)
时间复杂度渐进下届O(n)

下图是代码运行时，内部num，t，删除t后的样子。

def insert_sort(num):
    for i in range(1,len(num)):
        for j in range(i):
            if num[j]>num[i]:
                t=num[i]
                num.pop(i)
                num.insert(j,t)
    return num

选择排序

对于选择排序需要额外申请个空间，来存储已经排序好的序列。每次遍历都将最小或最大的元素找出来，放在最前或最后，等到全部遍历完，有序列表也就出来了。

def choose_sort(num):
    result=[]
    while num:
        mini=0
        for i in range(1,len(num)):
            if num[mini]>num[i]:  #选择一个最小的
                mini=i
        t=num[mini]
        num.pop(mini)
        result.append(t)
    return result

总结

对于上面几种排序，冒泡和插入是稳定性的排序算法，而选择排序是不稳定的算法。稳定与否是元素在排序前后相对应的位置不发生改变。
举个例子
当待排序序列[9,5,4,10,2,2*]出现相同元素时，稳定的算法排序好的样子是这样的[2,2*,4,5,9,10]，而不稳定的算法排序好的样子有可能是这样的[2*,2,4,5,9,10]。在2后加*号是为了方便看出位置的改变。