Python数据结构与算法 DAY 5

2221-李同学

发表文章数:27

热门标签

, , ,
首页 » Python » 正文

6.排序与搜索

排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。

排序算法的稳定性

稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。

当相等的元素是无法分辨的,比如像是整数,稳定性并不是一个问题。然而,假设以下的数对将要以他们的第一个数字来排序。

(4, 1)  (3, 1)  (3, 7)(5, 6)

在这个状况下,有可能产生两种不同的结果,一个是让相等键值的纪录维持相对的次序,而另外一个则没有:

(3, 1)  (3, 7)  (4, 1)  (5, 6)  (维持次序)(稳定的)
(3, 7)  (3, 1)  (4, 1)  (5, 6)  (次序被改变)(不稳定的)

不稳定排序算法可能会在相等的键值中改变纪录的相对次序,但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较,如此在其他方面相同键值的两个对象间之比较,(比如上面的比较中加入第二个标准:第二个键值的大小)就会被决定使用在原先数据次序中的条目,当作一个同分决赛。然而,要记住这种次序通常牵涉到额外的空间负担。

冒泡排序

冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下:

  • 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

冒泡排序的分析

交换过程图示(第一次):

Python数据结构与算法 DAY 5

那么我们需要进行n-1次冒泡过程,每次对应的比较次数如下图所示:

Python数据结构与算法 DAY 5

实现:

def bubble_sort(alist):
    """冒泡排序"""
    count = 0 #用于降低最优时间复杂度
    for j in range(1,len(alist)):
        for i in range(len(alist)-j):
            if alist[i]>alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
                count += 1
        if count == 0:
            return 

li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li) #[17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

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

冒泡排序演示

Python数据结构与算法 DAY 5

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

选择排序分析

排序过程:

Python数据结构与算法 DAY 5

Python数据结构与算法 DAY 5

实现:

def select_sort(alist):
    """选择排序"""
    for j in range(len(alist)-1):
        min_index = j  # 记录最小位置
        for i in range(j+1,len(alist)):
            if alist[min_index] > alist[i]:
                min_index = i
        alist[j],alist[min_index] = alist[min_index],alist[j]

时间复杂度

  • 最优时间复杂度:O(n^2)
  • 最坏时间复杂度:O(n^2)
  • 稳定性:不稳定(考虑升序每次选择最大的情况)

选择排序演示

Python数据结构与算法 DAY 5

插入排序

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

插入排序分析

Python数据结构与算法 DAY 5

Python数据结构与算法 DAY 5

实现:

def insert_sort(alist):
# 从第二个位置,即下标为1的元素开始向前插入
    for j in range(1,len(alist)): 
        for i in range(j,0,-1):
            if alist[i-1] > alist[i]:
                alist[i-1],alist[i] = alist[i],alist[i-1]
            else:
                break #降低最优时间复杂度

时间复杂度

  • 最优时间复杂度:O(n) (升序排列,序列已经处于升序状态)
  • 最坏时间复杂度:O(n^2)
  • 稳定性:稳定

插入排序演示

Python数据结构与算法 DAY 5

未经允许不得转载:作者:2221-李同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法 DAY 5》 发布于2021-10-12

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录