📊 算法/数据结构
Table of Contents
你将学习如下内容
- 算法
- 排序算法
- 数据结构
- 链表
课程列表
数据结构-链表
链表概念 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 特点 效率 插入：O（1） 访问：O（n） 由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间。 优点 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。 缺点 链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。 常见的链表 单向链表 单向循环链表 双向链表 双向循环链表 单向链表 单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。 链表是由结点构成，head 指针指向第一个成为表头结点，而终止于最后一个指向 NULL 的指针。
算法-排序算法
各排序算法的复杂度 内部排序和外部排序 内部排序，指的是待排序的几率存放在计算机随机存储器中进行的排序过程; 外部排序，指的是排序中要对外存储器进行访问的排序过程。 归并排序需要外部数组进行存储，来存放对半分隔的临时数组，所以是外部排序。 不稳定算法 稳定排序:若在待排序的记录中，存在两个或两个以上的关键码值相等的记录，经排序后这些记录的相对次序仍然保持不变，则称相应的排序方法是稳定的方法，否则是不稳定的方法。 判断算法是否稳定主要是看算法是否比较相邻元素，交换相邻元素，如果一个算法既比较相邻元素，又交换相邻元素，那么相等的元素不会彼此进行交换，那么相对次序永远不会变。 例如针对于数组 [5,….,5]，第一个 5 排在第二个 5 前面，那么当序列变为 […,5,5…] 时，两个 5 之间不会交换位置，那么相对次序肯定就不会变了，所以算法稳定。 堆排序比较的不是相邻元素，也不是交换相邻元素，所以不稳定。 快排比较的是相邻的元素，但是交换的不是相邻元素，所以不稳定。 选择排序比较的不是相邻元素，也不是交换相邻元素，所以不稳定。 希尔排序比较的不是相邻元素，也不是交换相邻元素，所以不稳定。 所以不稳定算法有：