首页 > 编程语言 >排序算法总结

排序算法总结

时间:2023-10-20 11:55:54浏览次数:37  
标签:总结 sort 元素 range li 算法 数组 排序

low B三人组

冒泡排序

  1. 思想:列表相邻元素两两对比,每趟结束都会产生一个最大/最小元素

  2. 代码实现

    def bubble_sort(li):
        for i in range(0,len(li)-1):  # 趟数
            exchange = 0     # 设置一个标识符,当有一趟无变化时,列表已有序,停止排序
            for j in range(0,len(li)-i-1):   # 每趟比较次数
                if li[j]>li[j+1]:
                    li[j+1],li[j] = li[j],li[j+1]
                    exchange = 1
            if exchange == 0:
                return
    import random
    li = list(range(10))
    random.shuffle(li)
    bubble_sort(li)
    print(li)
    

选择排序

  1. 思想:找到无序列表中的最大/最小元素,与无序列表中的第一个/最后一个元素交换位置

  2. 代码实现

    def Search_sort(li):
        for i in range(len(li)-1):  # 趟数
            min_loc=i           # 存放最小值数组下标并可预定义一个最小值方便比较
            for j in range(i+1,len(li)):   # 无序列表的比较
                if li[min_loc]>li[j]:
                    min_loc=j
            li[min_loc],li[i]=li[i],li[min_loc]     # 找出无需表中的最小值与当前排序趟数为下标(无序表中的第一个位置)的元素进行交换
    import random
    li=list(range(10))
    random.shuffle(li)
    Search_sort(li)
    print(li)
    

插入排序

  1. 思想:从无序列表中的元素一一插入到有序表中

  2. 代码实现

    def Insert_sort(li):
        for i in range(1,len(li)):   # 开始无序列表有n-1个元素
            tmp=li[i]    # 保存元素,为插入时,大的元素后移空出位置
            n=i-1         # 从后往前遍历有序列表
            while n>=0 and li[n]>tmp:     # 当有序元素未遍历完且有序元素大于待插元素时
                li[n+1]=li[n]               # 元素不断后移
                n -= 1
            li[n+1]=tmp
    import random
    li=list(range(10))
    random.shuffle(li)
    print(li)
    Insert_sort(li)
    print(li)
    

分析

  • 时间复杂度都为:O(n^2)

​ 原因:n表示元素个数,都要执行n趟(有n个元素需进行排序),每趟都需执行次数(即每个元素需与其他元素的比较次数)

  • 空间复杂度:O(1)(原地排序)

NB 三人组

快速排序

  1. 思想:采用递归思想,选取元素,将遍历列表,当列表中的元素大于所选元素,将其放置在所选元素的右边,反之放置左边

image

  1. 代码实现

    def quick_sort(li,left,right):
        tmp=li[left]            # 选定首位为待排元素
        while left<right:       # 当两元素不共同指向空位置时
            while left<right and li[right]>=tmp:        # 先从右边开始看,因为左边一开始为空
                right -= 1
            li[left] = li[right]
            while left<right and li[left]<=tmp:         # 再从左边开始看
                left += 1
            li[right]=li[left]
        li[left]=tmp        # 最后把空位留给待排元素
        return left         # 返回中间已排好元素的下标
    def sort(li,left,right):
        if left<right:  # 有两个或两个以上的元素(若不加则会出现死循环)
            mid=quick_sort(li,left,right)
            sort(li,left,mid-1)         # 左边
            sort(li,mid+1,right)        # 右边
    li=list(range(10))
    import random
    random.shuffle(li)
    print(li)
    sort(li,0,len(li)-1)
    print(li)
    

堆排序

  1. 思想:将二叉树建立成大/小根堆(”农村包围城市“思想),将大/小根堆取出与最后的叶子结点进行交换,并重新调整堆,循环上述步骤,最后得到已排好序的堆。

  2. 代码实现

    • 直接求法:
    # 归并排序
    # 堆调整(从大到小排序)
    def sift(li,low,high):    # 除根结点外,其余各结点为堆
        i=low      # 设置当前空的位置
        tmp=li[i]   # 存储待排元素(一开始存储在空位置上的元素)
        j=2*i+1      # 找到结点的左孩子
        while j<=high:  # 判断结点是否还具有孩子结点
            if j+1<=high and li[j+1]>li[j]:   # 比较左右孩子哪个更大
                j += 1
            if li[j]>tmp:   # 将大的元素放入父结点中
                li[i]=li[j]
                i = j       # i转换到新的空位置下标处
                j = 2*i+1     # j再次寻找新i的孩子结点
            else:              # 若i没有孩子大于待排元素,退出循环
                break
        li[i]=tmp       # 当tmp大于i位置上所有孩子或j超界,则将待排元素排入空位上
    def heap_sort(li,low,high):
        for i in range((high-1)//2,-1,-1):   # “农村包围城市”思想(下标为0的元素也需堆调整)
            sift(li,i,high)  # 完成堆的排序
        for j in range(high,0,-1):     # 最大与最小元素交换位置(省空间)
            li[j],li[low]=li[low],li[j]
            sift(li,low,j-1)
    li=list(range(10))
    import random
    random.shuffle(li)
    print(li)
    heap_sort(li,0,len(li)-1)
    print(li)
    
    • 内置模块(heapq)求法

      • heapq.heapify:建堆(小根堆)

      • heapq,heappop:取数(每次只取一个数)

        import heapq
        li=list(range(10))
        import random
        random.shuffle(li)
        print(li)
        heapq.heapify(li)    # 建堆
        for i in range(len(li)):
            print(heapq.heappop(li),end=" ")    # 取数
        

归并排序(代码易忘)

  1. 思想:先拆分后归并

  2. 代码实现

    # 归并排序
    def merge(li,low,mid,high):    # low表示第一个数组的第一个元素下标,mid表示第一第二个数组的分界线,high表示第二个数组的最后一个元素下标
        i = low
        j = mid+1           # j表示第二个数组的第一个元素下标
        ltmp=[]             # 定义一个空列表,以暂时保存排好序的元素
        while i<=mid and j<=high:   # 当各数组都有元素时
            if li[i]<li[j]:         
                ltmp.append(li[i])
                i += 1
            else:
                ltmp.append(li[j])
                j += 1
        while i<=mid:           # 当右边数组空时,将左边所有元素存放入新数组中
            ltmp.append(li[i])
            i += 1
        while j<=high:          # 当左边数组空时,将右边所有元素存放入新数组中
            ltmp.append(li[j])
            j += 1
        li[low:high+1]=ltmp     # 数组的切片可直接传递
    def merge_sort(li,low,high):    # 先拆分后合并
        if low<high:        # 当未拆分为都只剩1个元素的数组时
            mid = (low+high)//2     # 拆分方法
            merge_sort(li,low,mid)  # 在已拆分好的的基础上,继续对mid左边进行拆分
            merge_sort(li,mid+1,high)   # 在已拆分好的的基础上,继续对mid右边进行拆分
            merge(li,low,mid,high)      # 对左右两边拆分的数组以mid中间值进行合并
    li=list(range(10))
    import random
    random.shuffle(li)
    print(li)
    merge_sort(li,0,len(li)-1)
    print(li)
    

分析

  • 平均时间复杂度:O(nlogn)(存在折半排序,只用执行logn趟)
  • 空间复杂度:
    • 快速排序:平均空间复杂度为:O(logn)(哪怕没有使用数组空间,但使用了递归,会用到系统栈的空间)
    • 堆排序:O(1)
    • 归并排序:O(n)(新建了长度为n的数组)

其它排序

希尔排序(易忘)

  1. 思想:相当于插入排序,只是不是排序间隔不为1

  2. 代码实现

    # 希尔排序
    # 直接插入排序
    def Insert(li,gap):         # 以gap为中间间隔,对数组进行排序
        for i in range(gap,len(li)):    # 以第一个数组为有序对象,对后面数组进行对照排序
            tmp=li[i]
            j = i-gap
            while j>=0 and li[j]>tmp:   # 当后面数组对应元素小于前面数组的对应元素且前面对应元素存在时
                li[j+gap]=li[j]
                j -= gap
            li[j+gap]=tmp
    # 先拆分后插入排序
    def shell_sort(li):
        gap=len(li)//2
        while gap>=1:   # 当gap中间间隔为1时,表示最后一趟遍历排序,gap<1为终止条件
            Insert(li,gap)
            gap //= 2       # 能够使得循环结束语句
    li=list(range(10))
    import random
    random.shuffle(li)
    print(li)
    shell_sort(li)
    print(li)
    

计数排序(非比较排序)

  1. 思想:创建一个以数组最大值为范围的空间,并对数组元素进行计数,最后通过新数组中每个下标对应的数目进行输出

  2. 代码实现

    # 计数排序
    def count_sort(li):
        max_num=max(li)         # 找出待排序数组的最大值作为新数组的数组范围
        count=[0 for _ in range(max_num+1)]
        for i in li:        # 遍历待排序数组
            count[i] += 1       # 对每个在大小范围内的元素进行计数
        li.clear()          # 清空
        for ind,val in enumerate(count):
            for j in range(val):    # 当元素存在,则添加对应个数的数组值,若不存在则不添加
                li.append(ind)
    li=list(range(10))
    import random
    random.shuffle(li)
    print(li)
    count_sort(li)
    print(li)
    

基数排序

  1. 思想:存在多个关键字(适用于对数字排序)

  2. 代码实现

    # 基数排序
    def radix_sort(li):
        max_num=max(li)                         # 找到最大数,为找到关键字的个数
        t = 0                                   # 起始t为零,方便找出个位到最高位的数值
        while 10**t<=max_num:                   # 超出最大数范围则退出循环
            bucket=[[] for _ in range(10)]      # 每趟都要重新创建
            for i in li:                        # 遍历待排序数组元素
                num=i//10**t%10                 # 找到每个数组的关键字比较的大小
                bucket[num].append(i)           # 在对应的桶中添加元素
            li.clear()
            for j in bucket:
                li.extend(j)                    # extend可以一次性添加所有元素,参数可为可迭代对象,append则只能一次添加一个元素
            t += 1                              # 使得循环结束的条件式
    import random
    li=[random.randint(0,1000) for _ in range(10)]
    print(li)
    radix_sort(li)
    print(li)
    

稳定性分析

  • 如果是一步步调换比较排序的则为稳定排序,eg:冒泡排序,直接插入排序,归并排序
  • 如果是飞着调换比较的排序则为非稳定排序,eg:直接选择排序,快速排序,堆排序

标签:总结,sort,元素,range,li,算法,数组,排序
From: https://www.cnblogs.com/byyya/p/17776755.html

相关文章

  • 项目开发中遇到的问题总结
    1、echarts图表问题数据库中存储结构为横向一条数据包含体重,身高,血糖血压,添加事件等数据而前端需要纵向以属性为y轴,事件为纵轴,分别产生多张表格。需要前端使用javascript进行遍历,使用到了map方法this.status=response.data.dataconsole.log(this.status)constxData=thi......
  • 数据结构之美:如何优化搜索和排序算法
    文章目录搜索算法的优化1.二分搜索2.哈希表排序算法的优化1.快速排序2.归并排序总结......
  • 文心一言 VS 讯飞星火 VS chatgpt (106)-- 算法导论10.1 4题
    四、用go语言,重写ENQUEUE和DEQUEUE的代码,使之能处理队列的下溢和上溢。文心一言:在Go语言中,我们可以使用切片来实现队列。下面是如何实现ENQUEUE和DEQUEUE操作,同时处理队列的下溢和上溢的情况:packagemainimport"fmt"typeQueuestruct{elements[]i......
  • 文心一言 VS 讯飞星火 VS chatgpt (105)-- 算法导论10.1 3题
    三、用go语言,仿照图10-2,画图表示依次执行操作ENQUEUE(Q,4)、ENQUEUE(Q,1)、ENQUEUE(Q,3)、DEQUEUE(Q)、ENQUEUE(Q,8)和DEQUEUE(Q)每一步的结果,队列初始为空,存储于数组Q[1…6]中。文心一言:在这个问题中,我们尝试使用Go语言来模拟队列的操作,并且展示每一步的结果。首先,我们需要定义......
  • 文心一言 VS 讯飞星火 VS chatgpt (107)-- 算法导论10.1 5题
    五、用go语言,栈插入和删除元素只能在同一端进行,队列的插入操作和删除操作分别在两端进行,与它们不同的,有一种双端队列(deque),其插入和删除操作都可以在两端进行。写出4个时间均为O(1)的过程,分别实现在双端队列的两端插入和删除元素的操作,该队列是用一个数组实现的。文心一言:在Go......
  • 文心一言 VS 讯飞星火 VS chatgpt (104)-- 算法导论10.1 2题
    二、用go语言,说明如何在一个数组A[1…n]中实现两个栈,使得当两个栈的元素个数之和不为n时,两者都不会发生上溢。要求PUSH和POP操作的运行时间为O(1)。文心一言:在这个问题中,我们要在一个数组A[1…n]中实现两个栈,使得当两个栈的元素个数之和不为n时,两者都不会发生上溢。这......
  • 文心一言 VS 讯飞星火 VS chatgpt (103)-- 算法导论10.1 1题
    一、用go语言,仿照图10-1,画图表示依次执行操作PUSH(S,4)、PUSH(S,1)、PUSH(S,3)、POP(S)、PUSH(S,8)和POP(S)每一步的结果,栈S初始为空,存储于数组S[1…6]中。文心一言:图10-1展示了在执行一系列栈操作后栈的状态。我会用文字描述来模仿这个图,因为目前我无法直接绘制图片。栈S初始......
  • 10.20算法
    位1的个数编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为'1'的个数(也被称为汉明重量)。 提示:请注意,在某些语言(如Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号......
  • 智能优化算法第一次实验
    智能优化算法第一次实验一、实验目的(1)掌握梯度下降法的基础知识及其应用过程;(2)利用梯度下降法求解简单优化问题。二、实验原理梯度下降法是一种最优化算法,由于函数在该点梯度的模代表着函数值在该点最大的变化率,我们可以让函数沿着梯度方向迭代移动逼近函数最值,这就是梯......
  • [刷题笔记] [算法学习笔记]树上差分 -- Luogu P3128
    DescriptionProblem:https://www.luogu.com.cn/problem/P3128FJ给他的牛棚的\(N\)个隔间之间安装了\(N-1\)根管道,隔间编号从\(1\)到\(N\)。所有隔间都被管道连通了。FJ有\(K\)条运输牛奶的路线,第\(i\)条路线从隔间\(s_i\)运输到隔间\(t_i\)。一条运输路线会给......