python排序算法汇总

入门小菜鸟,希望像做笔记记录自己学的东西,也希望能帮助到同样入门的人,更希望大佬们帮忙纠错啦~侵权立删。

目录

一、冒泡排序

二、选择排序

三、插入排序

四、快速排序

五、归并排序

六、希尔排序


一、冒泡排序

比较两个相邻元素的大小,然后根据大小交换位置,这样从列表左端开始冒泡,最后最大值会依次从右端冒出。

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

时间复杂度为O(n²)


二、选择排序

把序列中的最小值或者最大值找出来放在起始位置,然后再从剩下的序列中找出极值放到起始位置之后,以此类推最后就完成排序。

def select(data):
    l = len(data)
    for i in range(l-1):
        t = i
        for j in range(i+1,l):
            if data[j] > data[t]:
                j,t = t,j
        if t != i:
            data[i],data[t] = data[t],data[i]
    return data

时间复杂度为O(n²)


三、插入排序

首先构建一个初始的有序序列,然后从无序序列中抽取元素,插入到有序序列的相对排序位置。

简单来说就是从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置。

很适合用在合并两个有序序列,并且合并后的序列依旧有序这样的情况下。

def insert(data):
    l = len(data)
    for i in range(1,l):
        for j in range(i,0,-1):
            if data[j] < data[j-1]:
                data[j],data[j-1] = data[j-1],data[j]
    return data

时间复杂度为O(n²)


四、快速排序

从序列中找出一个基准元素,大于该元素的放到一边,小于该元素的放到另一边形成分区;然后分别从大小分区中再找基准再分别分出相对大小分区,通过递归完成快速排序。

def quick(data):
    if len(data) >= 2:
        m = data[0] #基准值,随你取
        #左右分区
        l = []
        r = []
        data.remove(m)
        for i in data:
            if i >= m:
                r.append(i)
            else:
                l.append(i)
        return quick(l) + [m] + quick(r)
    else:
        return data

这种算法可以通过一些方式提高速度,比如说使用并行的元素分区,在超大数据中使用多机进行联合排序,将两个分区拆分为更多分区等。


五、归并排序

将数据分为两个数组,然后比较两个数组最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

def merge(data):
    #分治操作
    length = len(data)
    if length <= 1:
        return data
    n = length//2
    left = merge(data[:n])
    right = merge(data[n:])
    #合并操作
    l,r = 0,0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l = l + 1
        else:
            result.append(right[r])
            r = r + 1
    result = result + left[l:]
    result = result + right[r:]
    return result

六、希尔排序

希尔排序按照下标的增量对数据进行分组,对每组使用直接插入排序算法排序,然后随着下标增量的减少,每组包含的数据越来越多,当增量减至1时恰好分成一组,输出即为最终结果。

思想:随着进行相对比较的两个元素之间的距离的减小,相对元素的大小会逐步区分出来并向两端聚拢,当步长为1的时候,就完成最后一次比较,那么序列顺序就出来了。

def xier(data):
    l = len(data)
    s = l // 2
    while s > 0:
        for i in range(s,l):
            t = i
            while t >= s and data[t - s] > data[t]:
                data[t - s],data[t] = data[t],data[t-s]
                t = t - s
        s = s // 2
    return data

欢迎大家在评论区批评指正,谢谢~

上一篇:栈和队列的基本操作


下一篇:假装有标题 打卡2