【算法】算法学习二:链表 & 数组 & 选择排序

这篇具有很好参考价值的文章主要介绍了【算法】算法学习二:链表 & 数组 & 选择排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、链表和数组

链表和数组是常见的数据结构,用于组织和存储数据。它们在内部实现和使用方式上有一些显著的区别。

数组是一个连续的内存块,用于存储相同类型的元素。数组的每个元素通过索引访问,索引从0开始。数组的主要特点包括:

  1. 随机访问:由于数组的元素在内存中是连续存储的,因此可以通过索引以常量时间(O(1))的复杂度访问任何元素。
  2. 固定大小:数组的大小在创建时确定,并且通常无法更改。如果需要更多的空间,可能需要创建一个新的更大的数组并将数据复制到新数组中。

链表是由节点组成的集合,每个节点包含数据和指向下一个节点的引用(或指针)。链表的主要特点包括:

  1. 非连续存储:链表的节点可以在内存中的任意位置,它们通过指针连接起来。这使得链表的插入和删除操作比数组更高效。
  2. 顺序访问:要访问链表中的元素,需要从头节点开始按顺序遍历链表,直到找到所需的元素。因此,链表的访问时间复杂度是O(n),其中n是链表的长度。
  3. 动态大小:链表的大小可以根据需要动态增长或缩小,不像数组需要预先定义大小。

链表和数组各有优劣,适用于不同的场景:

  • 当需要频繁地进行随机访问,并且已知元素的数量不会变化时,数组是一个较好的选择。
  • 当需要频繁地进行插入和删除操作,或者元素数量可能动态变化时,链表更加适合。链表的动态调整大小的能力使得它在需要频繁插入和删除的场景下更具优势。

需要注意的是,数组和链表也有一些变体和扩展,例如动态数组、双向链表、循环链表等,它们根据不同的需求和应用场景提供了更多的功能和灵活性。

链表和数组在常见操作的运行时间上有一些不同。

访问元素:

  • 数组:通过索引可以直接访问指定位置的元素,时间复杂度为 O(1)。
  • 链表:需要从头节点开始逐个遍历,直到找到目标节点,时间复杂度取决于链表的长度,最坏情况下为 O(n)。

插入和删除元素:

  • 数组:插入和删除元素需要移动其他元素以保持连续性,平均情况下需要移动一半的元素,因此时间复杂度为 O(n)。如果在末尾插入或删除元素,时间复杂度为 O(1)。
  • 链表:插入和删除元素只需要改变节点的指针,时间复杂度为 O(1),不需要移动其他元素。

综上所述,数组在随机访问和末尾插入/删除操作上更快,而链表在头部插入/删除和元素的顺序性变化较多的情况下更快。选择使用哪种数据结构取决于具体的使用场景和对各种操作的需求。

二、选择排序(含示例代码)

选择排序(Selection Sort)是一种简单的排序算法。它的基本思想是每次从未排序的部分选择最小(或最大)的元素,然后将其与未排序部分的第一个元素交换位置。重复这个过程,直到整个序列排序完成。

选择排序的算法步骤如下:

  1. 找到未排序部分中的最小元素。
  2. 将最小元素与未排序部分的第一个元素交换位置。
  3. 将排序的边界向右移动一个位置,将已排序部分扩大一个元素。
  4. 重复步骤1~3,直到排序完成。

选择排序的时间复杂度是 O(n^2),其中 n 是待排序序列的长度。无论输入数据的初始顺序如何,选择排序都需要进行 n-1 次比较和交换操作。虽然选择排序在简单性和实现上是比较容易的,但对于大规模的数据集来说,效率较低,因此在实际应用中不常使用。

示例代码如下:

def get_small_num(arr):
    small_num = arr[0]
    small_idx = 0
    for i in range(1, len(arr)):
        if arr[i] < small_num:
            small_num = arr[i]
            small_idx = i
    return small_idx

def slection_sort(arr):
    new_arr = []
    for i in range(len(arr)):
        small = get_small_num(arr)
        new_arr.append(arr.pop(small))
    return new_arr

arr = [5, 3, 8, 4, 1, 0, 2]
slection_sort(arr)
  • arr.pop(small) - 从列表 arr 中删除索引为 small 的元素,并返回被删除的元素的值。
  • new_arr.append(…) - 将返回的被删除元素的值追加到列表 new_arr 的末尾。

pop() 函数是用于从列表中删除指定索引位置的元素,并返回该元素的值。

语法:

list.pop(index)

参数:

  • index:要删除元素的索引位置。如果不指定索引,默认为列表的最后一个元素。

返回值:

  • 返回被删除元素的值。

示例如下所示:

my_list = [1, 2, 3, 4, 5]
removed_element = my_list.pop(2)
print(my_list)  # 输出: [1, 2, 4, 5]
print(removed_element)  # 输出: 3

在上面的示例中,pop(2) 删除了列表 my_list 中索引为 2 的元素,即值为 3 的元素。然后,pop() 函数返回被删除的元素值为 3。最后,打印 my_list 结果为 [1, 2, 4, 5],打印 removed_element 结果为 3。文章来源地址https://www.toymoban.com/news/detail-460350.html

到了这里,关于【算法】算法学习二:链表 & 数组 & 选择排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】排序算法:冒泡排序,冒泡排序优化,选择排序、选择排序优化

    目录 一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 代码实现: 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析  代码实现: 1、冒泡排序思想 冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将最大(或最小)的元素移到右边(或左边

    2024年01月19日
    浏览(49)
  • 面试算法78:合并排序链表

    输入k个排序的链表,请将它们合并成一个排序的链表。 用k个指针分别指向这k个链表的头节点,每次从这k个节点中选取值最小的节点。然后将指向值最小的节点的指针向后移动一步,再比较k个指针指向的节点并选取值最小的节点。重复这个过程,直到所有节点都被选取出来

    2024年02月03日
    浏览(38)
  • 【算法】Java-使用数组模拟单向链表,双向链表

    目录 试题1:实现一个单链表,并实现以下功能: 试题2:实现一个双链表,并实现以下功能 思路总结: 什么情况下可能涉及到用数组实现链表呢?       在学习时了解到了可以用数组模拟链表,使其兼顾数据查找快,链表新增和删除快的缺点,找来一些试题实现了下,如下

    2024年02月09日
    浏览(46)
  • 【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:算法百炼成神 本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面

    2024年02月17日
    浏览(58)
  • 【算法】排序——选择排序和交换排序(快速排序)

     ========================================================================= 主页点击直达: 个人主页 我的小仓库: 代码仓库 C语言偷着笑: C语言专栏 数据结构挨打小记:初阶数据结构专栏 Linux被操作记:Linux专栏 LeetCode刷题掉发记:LeetCode刷题 算法头疼记:算法专栏  =========================

    2024年02月08日
    浏览(43)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(81)
  • 排序算法(一) -- 选择排序和冒泡排序

    选择排序和冒泡排序是我们初学C语言必学的两种简单的排序算法,也是我们以后学习数据结构与算法课程中更复杂的排序算法的基础。本文用由浅入深的逻辑条理,试图将这两种排序算法讲解清楚。 本文所有的排序均是针对一维数组的,全文所用的一维数组的例子如下: 一

    2024年02月06日
    浏览(32)
  • 排序算法之详解选择排序

    选择排序顾名思义是需要进行选择的,那么就要问题了,选择到底是选择什么呢? 选择排序的选择是 选择 数组中 未排序的数组 中 最小的值 ,将被选择的元素放在 未排序数组 的 首位 如果你对 ‘未排序数组’ , ‘选择’ 的概念不理解,那么你可以看看下面的图 有了上面

    2023年04月25日
    浏览(45)
  • 排序算法:选择排序

    选择排序的思想是:双重循环遍历数组,每经过一轮比较,找到最小元素的下标,将其交换至首位。         选择排序就好比第一个数字站在擂台上,大吼一声:“还有谁比我小?”。剩余数字来挨个打擂,如果出现比第一个数字小的数,则新的擂主产生。每轮打擂结束

    2024年02月11日
    浏览(80)
  • 【算法系列 | 3】深入解析排序算法之——选择排序

    你只管努力,其他交给时间,时间会证明一切。 文章标记颜色说明: 黄色 :重要标题 红色 :用来标记结论 绿色 :用来标记一级论点 蓝色 :用来标记二级论点 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力

    2024年02月08日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包