数据结构4 – 排序和查找

夏天老师

发表文章数:629

热门标签

首页 » 数据结构 » 正文

排序

排序算法是一种能将一串数据依照特定顺序进行排序的一种算法

排序算法的稳定性

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

demo

以下的树对将要以他们的第一个数字进行排序

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

这个状况会有两个结果

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

so,不稳定的排序算法可能会在相等的键值对中改变记录的相对次序,但是稳定排序算法从来不会。

冒泡排序

越小的元素会经由交换慢慢"浮"到数列的顶部

冒泡排序(Bubble Sort)是一种相对简单的排序算法。它重复的遍历要排序的数列,一次比较两个元素。
遍历数列的工作是重复的进行直到没有再需要交换,也就是说该数列已经排序完成。

数据结构4 - 排序和查找

逻辑运作

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

示意图

交换过程(第一次交换)
数据结构4 - 排序和查找

共进行n-1次冒泡排序

代码实现

def bubble_sort(alist):
    for j in range(len(alist)-1,0,-1):
        # j表示每次遍历需要比较的次数,是逐渐减小的
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

时间复杂度

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

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。

工作原理:首先在未排序序列中找到最大(小)值,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最大(小)值,然后再放到起始位置。以此类推,排序完毕。
数据结构4 - 排序和查找

逻辑运作

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

示意图

数据结构4 - 排序和查找

代码实现

def selection_sort(alist):
    n = len(alist)
    # 需要进行n-1次选择操作
    for i in range(n-1):
        # 记录最小位置
        min_index = i
        # 从i+1位置到末尾选择出最小数据
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        # 如果选择出的数据不在正确位置,进行交换
        if min_index != i:
            alist[i], alist[min_index] = alist[min_index], alist[i]

时间复杂度

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

插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法

它的工作原理是通过构建有序序列,对于无排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

数据结构4 - 排序和查找

逻辑运作

插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

示意图

数据结构4 - 排序和查找

代码实现

def insert_sort(alist):
    # 从第二个位置,即下标为1的元素开始向前插入
    for i in range(1, len(alist)):
        # 从第i个元素开始向前比较,如果小于前一个元素,交换位置
        for j in range(i, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]

时间复杂度

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

快速排序

快速排序(Quicksort)通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据要比另外一部分的所有数据小,然后再按照此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据编程有序序列。

数据结构4 - 排序和查找

逻辑运作

  1. 从数列中挑出一个元素,称为"基准"(pivot)
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,比基准值大的放基准后面。在这个分区结束后,该基准就处于数列的中间位置。这个称为分区操作
  3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

示意图

数据结构4 - 排序和查找

代码实现

def quick_sort(alist, start, end):
    """快速排序"""

    # 递归的退出条件
    if start >= end:
        return

    # 设定起始元素为要寻找位置的基准元素
    mid = alist[start]

    # low为序列左边的由左向右移动的游标
    low = start

    # high为序列右边的由右向左移动的游标
    high = end

    while low < high:
        # 如果low与high未重合,high指向的元素不比基准元素小,则high向左移动
        while low < high and alist[high] >= mid:
            high -= 1
        # 将high指向的元素放到low的位置上
        alist[low] = alist[high]

        # 如果low与high未重合,low指向的元素比基准元素小,则low向右移动
        while low < high and alist[low] < mid:
            low += 1
        # 将low指向的元素放到high的位置上
        alist[high] = alist[low]

    # 退出循环后,low与high重合,此时所指位置为基准元素的正确位置
    # 将基准元素放到该位置
    alist[low] = mid

    # 对基准元素左边的子序列进行快速排序
    # 最好的情况是遍历平衡二叉树
    quick_sort(alist, start, low-1)

    # 对基准元素右边的子序列进行快速排序O(nlogn)
    # 最差的情况只有左或右节点的单斜树O(n)
    quick_sort(alist, low+1, end)

时间复杂度

  • 最优时间复杂度O(nlogn)
  • 最坏时间复杂度O(n^2)
  • 稳定性:不稳定

希尔排序

希尔排序(Shell Sort)的基本思想是:将数组列在一个表中并对分别进行插入排序,重复这过程,不过每次用更长的列(步长更长了,列数更少了)来进行。最后整个表就只有一列了。

将数组转换至表是为了更好的理解这算法,算法本身还是使用数组进行排序的

数据结构4 - 排序和查找

逻辑运作

假设我们有一组数
[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中更好的描述算法。

13 14 94 33 82 
25 59 94 65 23 
45 27 73 25 39 
10 

然后我们对每列进行排序

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字,依次接在一起我们得到

[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]

这时10已经移步到正确位置,然后再以3为步长进行排序

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序后

10 14 13
25 23 33
27 25 59
39 65 73
45 94 73
45 94 82
94

最后以1步长进行排序(此时就是简单的插入排序了)

示意图

数据结构4 - 排序和查找

代码实现

def shell_sort(alist):
    n = len(alist)
    # 初始步长
    gap = n / 2
    while gap > 0:
        # 按步长进行插入排序
        for i in range(gap, n):
            j = i
            # 插入排序
            while j>=gap and alist[j-gap] > alist[j]:
                alist[j-gap], alist[j] = alist[j], alist[j-gap]
                j -= gap
        # 得到新的步长
        gap = gap / 2

时间复杂度

  • 最优时间复杂度:根据步长序列的不同而不同
  • 最坏时间复杂度:O(n^2)
  • 稳定想:不稳定

归并排序

归并排序是采用分治法的一个非常典型的应用。

归并排序的思想就是先递归分解数组,再合并数组。

数据结构4 - 排序和查找

逻辑运作

将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

示意图

数据结构4 - 排序和查找

代码实现

def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    # 二分分解
    num = len(alist)/2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    # 合并
    return merge(left,right)

def merge(left, right):
    '''合并操作,将两个有序数组left[]和right[]合并成一个大的有序数组'''
    #left与right的下标指针
    l, r = 0, 0
    result = []
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

时间复杂度

  • 最优时间复杂度:O(nlogn)
  • 最坏时间复杂度:O(nlogn)
  • 稳定性:稳定

常见排序算法效率比较

数据结构4 - 排序和查找

查找

搜索是在一个项目集合中找到一个特定项目的算法过程。
搜索通常的答案是真的或假的,因为该项目是否存在。
搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找

二分法查找

二分查找
优点:次数少,查找速度快,平均性能好
缺点:待查表为有序表,插入删除困难
so,二分法适用于不经常变动而查找频繁的有序列表。

查找逻辑

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

二分法查找实现

非递归实现

def binary_search(alist, item):
      first = 0
      last = len(alist)-1
      while first<=last:
          midpoint = (first + last)/2
          if alist[midpoint] == item:
              return True
          elif item < alist[midpoint]:
              last = midpoint-1
          else:
              first = midpoint+1
    return False

递归实现

def binary_search(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint]==item:
          return True
        else:
          if item<alist[midpoint]:
            return binary_search(alist[:midpoint],item)
          else:
            return binary_search(alist[midpoint+1:],item)

时间复杂度

  • 最优时间复杂度:O(1)
  • 最坏时间复杂度:O(logn)
标签:

拜师教育学员文章:作者:夏天老师, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《数据结构4 – 排序和查找》 发布于2020-09-16

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录