数据结构算法--2 冒泡排序,选择排序,插入排序

简介: **基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**

基础排序算法


     冒泡排序


思想就是将相邻元素两两比较,当一个元素大于右侧相邻元素时,交换他们的位置,小于右侧元素时,位置不变,最终序列中的最大元素,像气泡一样,到了最右侧。




  • 这时冒泡排序第一轮结束,数列最右侧元素9的位置可认为是一个有序区,有序区目前有一个元素.
  • 第二轮排序结束后,数列右侧的有序区有了两个元素.



于该排序算法每一轮都要遍历所有元素,平均时间复杂度为O(n*n)


def bubble_sort(li):  
    for i in range(len(li)-1):  # 第i趟
        for j in range(len(li)-i-1):
            if li[j]>li[j+1]:   # 降序就改一下符号
                li[j],li[j+1]=li[j+1],li[j]   
 
li=[random.randint(1,100) for i in range(20)]
bubble_sort(li)
print(li)


如果在某一趟排序中列表没有发生变化,认为已经排好序,这时如果for循环遍历就极大浪费时间,我们可以加每一趟遍历前加一个标志位,在交换元素的代码处加一个修改标志位,这样就可以避免最坏情况出现.


def bubble_sort(li):
    for i in range(len(li)-1):
        exchange=False
        for j in range(len(li)-i-1):
            if li[j]>li[j+1]:
                li[j],li[j+1]=li[j+1],li[j]
                exchange=True
        print(li)  # 看每一趟的变化
        if not exchange:
            return


选择排序


基础思想为将列表中最小元素依次遍历筛选出来,最终得到一个有序列表


def select_sort_simple(li):
    li_new=[]
    for i in range(len(li)):   # 一共需要拿i次
        min_val=min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new


这个算法虽然简单但是浪费内存,我们可以在列表内部遍历,找到最小元素后与第一个元素交换位置,左侧有序区就有了第一个元素.


def select_sort(li):
    for i in range(len(li)-1):   # i趟,每次都把最小的放到前边交换
        min_loc=i   # 默认第一个最小,与后边遍历比较
        for j in range(i+1,len(li)):
            if li[j]<li[min_loc]:
                min_loc=j    # 目前的最小元素索引
        li[i],li[min_loc]=li[min_loc],li[i]
    return li


插入排序




^ 初始时手里(有序区)只有一张牌(默认为元素第一个值)。

^ 每次从无序区(列表右侧区)摸一张牌(依次遍历),插入到有序区的正确(按大小)位置。


def insert_sort(li):
    for i in range(1,len(li)):  # 功n-1,i表示摸到牌的下标
        tmp=li[i]  # 每次摸的牌
        j=i-1      # 手里最右侧的
        while j>=0 and li[j]>tmp:    # 一直往左走
            li[j+1]=li[j]    # 右移
            j-=1
        li[j+1]=tmp   # 选好位置了


可以看出插入排序时间复杂度为O(n*n)


相关文章
|
2月前
|
搜索推荐 算法 Go
Go语言数组排序(冒泡排序法)—— 用最直观的方式掌握排序算法
本案例介绍使用冒泡排序对整数数组进行升序排序的实现方法,涵盖输入处理、错误检查与排序逻辑。通过代码演示和算法解析,帮助理解排序原理及Go语言切片操作,为学习更复杂排序算法打下基础。
|
2月前
|
搜索推荐
选择排序与其它排序算法比较
选择排序与冒泡排序同属O(n²)排序算法,但选择排序不稳定。相比堆排序,虽每轮均选最大元素,但选择排序基于线性结构,效率较低,而堆排序利用大顶堆结构提升了选择效率。
38 0
|
2月前
|
搜索推荐
冒泡排序与其它排序算法比较
本内容比较了冒泡排序、选择排序和插入排序的特性。三者时间复杂度均为O(n²),但交换次数和稳定性不同。冒泡排序稳定,交换次数多,可优化至O(n);选择排序不稳定,交换次数少;插入排序交换次数最少,且二者均为稳定排序。对于有序数组,冒泡和插入可优化提升效率。
46 0
|
10月前
|
搜索推荐 Python
利用Python内置函数实现的冒泡排序算法
在上述代码中,`bubble_sort` 函数接受一个列表 `arr` 作为输入。通过两层循环,外层循环控制排序的轮数,内层循环用于比较相邻的元素并进行交换。如果前一个元素大于后一个元素,就将它们交换位置。
245 67
|
11月前
|
搜索推荐
冒泡排序算法
【10月更文挑战第19天】冒泡排序是一种基础的排序算法,虽然在实际应用中可能不是最优的选择,但对于理解排序算法的基本原理和过程具有重要意义。
|
11月前
|
搜索推荐 C语言
排序算法--冒泡排序
排序算法--冒泡排序
63 0
|
4天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
5天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
|
7天前
|
负载均衡 算法 调度
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
73 11
|
7天前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)

热门文章

最新文章