数据结构与算法Day5 排序算法

1187-吴同学

发表文章数:41

首页 » 数据结构 » 正文

排序算法(Sorting algorithm)

一种能将一串数据依照特定顺序进行排列的一种算法。
稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。即,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。

冒泡排序(Bubble Sort)

重复地遍历要排序的数列,一次比较两个元素。若比较的这两个元素顺序错误就交换顺序。遍历数列的工作重复地进行,直到不再需要交换,说明该数列已经排序完成。

算法原理:

  1. 比较相邻的元素,若第一个比第二个大则交换(升序)。
  2. 移到下一个位置,对相邻元素做同样的工作,直到最后第二个位置(结尾的最后一对)。
    一轮后,最后的元素是最大的数,不再进入排序。
  3. 对剩下的元素重复以上的步骤,直到没有任何一对数字需要比较。

数据结构与算法Day5 排序算法

算法实现

用顺序表、链表实现的不同,在于元素地址交换,一个是交换两个位置保存的数据,一个是交换节点(链接区需要重新排布),本质是相同的。(下面其他算法同)

def Bubble_sort(alist):
    """冒泡排序"""
    for i in range(len(alist)-1):
        #外层控制走多少次 
        for j in range(len(alist)-i-1):
            #内层控制从头走到“尾”
            if alist[j]>alist[j+1]:
                alist[j],alist[j+1]=alist[j+1],alist[j]
    return alist

优化实现

一旦轮次检测到顺序排列,则跳出循环。

def Bubble_sort(alist):
    """冒泡排序"""
    for i in range(len(alist)-1):
        #外层控制走多少次 
        count=0
        for j in range(len(alist)-i-1):
            #内层控制从头走到“尾”
            if alist[j]>alist[j+1]:
                alist[j],alist[j+1]=alist[j+1],alist[j]
                count+=1
        if count==0:
            break
    return alist

时间复杂度

最优时间复杂度:

O

(

n

)

O(n)

O(n)(表示遍历一次发现没有任何可以交换的元素,排序结束。)
最坏时间复杂度:

O

(

n

2

)

O(n^2)

O(n2)
稳定性:稳定

数据结构与算法Day5 排序算法

选择排序(Selection sort)

算法原理

  1. 在未排序序列中找到最小(大)元素,与起始位置的元素交换位置
  2. 从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列后的末尾,直到所有元素排序完毕。
    数据结构与算法Day5 排序算法

算法实现

def selection_sort(alist):
    """选择排序"""
    n=len(alist)
    for i in range(n-1):#最后第二个确定的时候,最后一个自然就确定了
        min_index=i
        for j in range(i+1,n):
            if alist[min_index]>alist[j]:
                min_index=j
        if alist[min_index]!=alist[i]:
            alist[i],alist[min_index]=alist[min_index],alist[i]
    return alist

时间复杂度

最优时间复杂度:

O

(

n

2

)

O(n^2)

O(n2)
最坏时间复杂度:

O

(

n

2

)

O(n^2)

O(n2)
稳定性:不稳定(考虑升序每次选择最大的情况)

插入排序

算法原理

  1. 构建有序序列,其后为未排序序列
  2. 取出未排序数据的首位
  3. 对有序序列从后向前扫描元素,若元素与取出的首位顺序不符则交换位置,直到顺序正确
  4. 重复上述步骤知道未排序序列为空。
    数据结构与算法Day5 排序算法

算法实现

def insert_sort(alist):
    for i in range(1,len(alist)):
        tem=alist[i]
        for j in range(i-1,-1,-1): 
            if tem <alist[j]:      
                alist[j+1],alist[j]=alist[j],alist[j+1]
            else:
                break
    return alist 

def insert_sort(alist):
    for i in range(1,len(alist)):
        #j代表内层循环起始值
        j=i
        while j>0:
            if alist[j-1]>alist[j]:      
                alist[j-1],alist[j]=alist[j],alist[j-1]
                j-=1
            else:
                break
    return alist   

时间复杂度

最优时间复杂度:

O

(

n

)

O(n)

O(n) (升序排列,序列已经处于升序状态)
最坏时间复杂度:

O

(

n

2

)

O(n^2)

O(n2)
稳定性:稳定

未经允许不得转载:作者:1187-吴同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《数据结构与算法Day5 排序算法》 发布于2020-12-01

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录