线性索引查找

索引：就是把一个关键字与它对应的记录相关联的过程。 索引按照结构可以分为线性索引、树形索引和多级索引。 线性索引：就是将索引项集合组织为线性结构，也称为索引表。 1 稠密索引 稠密索引：在线性索引中，将数据集中的每个记录对应一个索引项，索引项按照关键码有序排列。 但数据量大时，可能由于内存有限， ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

散列(Hash)表

1 散列表查找定义 散列技术：是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f (key)。 散列函数：对应关系 f 。又称为哈希 (Hash) 函数。 散列表：采用散列技术存储记录的一块连续的存储空间。又称为哈希表 (Hash table ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

多路查找树(B 树)

多路查找树：每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。 1、2-3 树 2-3 树：每一个结点都具有两个孩子 (2 结点) 或三个孩子 (3 结点) 的多路查找树 2 结点：包含一个元素和两个孩子(或没有孩子) ，左小右大。 3 结点：包含一小一大两个元素和三个孩子(或没有孩 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

排序的基本概念与分类

1 排序的基本概念 假设含有 n 个记录的序列为{r1,r2,…,rn} ，其相应的关键字分别为{k1,k2,…,kn} ，需确定 1,2,…,n 的一种排列 p1,p2,…,pn，使其相应的关键字满足 kpl<=kp2<=…<=kpn (非递减或非递增) 关系，即使得序列成为一个 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 04 排序

插入排序

1 直接插入排序 直接插入排序(Straight Insertion Sort) 的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序袭。 思路 如第 0 到 5 范围内的数从小到大排列，第六个数记为 temp，此时第 temp 比第 5 个数小，那么第 5 个 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 04 排序

选择排序

1 简单选择排序 简单选择排序法 (Simpple Selection Sort) 就是通过 n - i 次关键字间的比较，从 n- i + 1 个记录中选出关键字最小的记录，并和第 i ( 1 <= i <= n) 个记录交换之。 思路：遍历第i到第n个，找到i到n范围内最小的数，然 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 04 排序

分配排序

1 计数排序 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 04 排序

交换排序

1 冒泡排序 冒泡排序 (Bubble Sort) 一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。 思路 从第 0 个到第 n 个，和相邻的元素进行相比，如果比相邻的大的话，那么就交换二者顺序，这样的话 0 到 n 范围内的最大的数就放到 n 的位 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 04 排序

外部排序

外部排序的基本思想就是归并排序。 1 二路平衡归并 按照内存大小，将大文件分成若干长度为 l 的子文件（l 应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序（排好序的子文件统称为“归并段”或者“顺段”），将排好序的归并段重新写入外存，为下一个子文件排序腾出 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 04 排序

排列

题目出处 Leetcode 46. 全排列（没有重复） Leetcode 47. 全排列 II（包含重复） 剑指 Offer - 38 - 字符串的排列 面试实际遇到过 - Shopee 字符串的排列 1 题目描述 输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc， ...
2019-12-25 01 数据结构与算法 > 算法题 > 回溯搜索