【概述】

以查字典为例，在英文字典中查 “apple” 时，下意识的会翻开前面的书页，当查 “zoo” 时，下意识的翻开一定是后面的书页，显然，此时还绝对不是从中间开始查起，而且有一定目的地从前或从后查找

同样的，以取值范围在 $1$ 到 $10000$ 间的从小到大均匀分布在数组中的 $100$ 个元素为例，若要查找元素 $5$，那么自然而然的会考虑从数组下标较小的开始查找

【概述】

分块索引，又称索引顺序查找，其吸取了顺序查找和二分查找的优点，属于线性索引结构，既适用于静态索引，又适用于动态索引

其基本思想是将查找表分为若干子块，这些子块之间满足分块有序这个要求，即这些块满足以下两个条件：

【概述】

稠密索引常见于静态索引中，在线性索引里，若文件中的每个记录对应一个索引项，则这种索引称为稠密索引

在稠密索引中，无论文件是否按关键码有序，索引项总是按关键码有序进行排列

【概述】

在进行数据查找操作，当数据量不是很大时，一般的查找技术足以满足需求

但对于服务器来说，其是以大型数据库为中心的，并且其将大型数据库作为文件存放于外存中的，而当需要进行数据查找操作时，查找技术处理过于缓慢，为加快查找速度，设计出了索引这种结构

无论什么时候，每当想起自己曾满怀激情、兴奋、惊奇与真诚等等情绪，在键盘上敲出的第一个程序——“Hello World”，就总是会充满一种不知名的情绪

记得很久很久以前对 G 说过，真正地程序员都是一群充满好奇心的为解决问题甚至不眠不休并以此为乐的疯子，他们之中有人简单纯粹内心火热，有人善于分享乐于助人，也有人沉默寡言不苟言笑，还有人孤僻冷漠难以相处，但他们无一不是理想主义者，从敲出 “Hello World” 的那一刻起，他们的最初梦想和最终目的，就是为了改变这个世界

从最开始接触计算机至今大约有 8、9 个年头了，儿时大多只是瞎捣鼓，真正开始接触编程后，又因为种种原因没有 Blog，最近决定建一个属于自己的 Blog

【基本思想】

计数排序是非比较类排序一种，其基本思想是：对于给定的输入序列中的每一个元素 $x$，确定该序列中值小于 $x$ 的元素的个数，一旦有了这个信息，就可以将 $x$ 直接存放到最终的输出序列的正确位置上

例如，如果输入序列中只有 $17$ 个元素的值小于 $x$ 的值，则 $x$ 可以直接存放在输出序列的第 $18$ 个位置上

【基本思想】

基数排序借助多关键字排序的思想，对单逻辑关键字进行排序，简单来说，其是基于关键字各位的大小进行排序

假设长度为 $n$ 的线性表中每个结点 $a_j$ 的关键字由 $d$ 元组 $(k_j^{d_-1},k_j^{d_-2},…,d_j^1,d_j^0)$ 组成，满足 $0\leq k_j^i\leq r-1$，其中 $k_j^{d-1}$ 为最主关键字，$k_j^0$ 为最次关键字，且 $0\leq j <n,0\leq i\leq d-1$

【基本思想】

桶排序，是非比较排序中最简单一种排序方法，适用于待排序数据值域较大但分布比较均匀的情况

其基本思想是：假设待排序记录的值都在 $0$ 到 $m-1$ 之间，那么就设置 $m$ 个桶，将值为 $i$ 的记录分配到第 $i$ 个桶中，然后再将各个桶中的数据依次收集起来

【问题】

设 $A$ 为一个有 $n$ 个数字的有序集，其中所有数字各不相同，如果存在整数 $i,j$，使得 $1\leq i < j \leq n$ 且 $A[i]>A[j]$，则 $\{A[i],A[j]\}$ 这个有序对称为 $A$ 的一个逆序对

例如：集合 $\{3,1,4,5,2\}$ 的逆序对有 $\{3,1\}$、$\{3,2\}$、$\{4,2\}$、$\{5,2\}$ 共 $4$ 个

【基本思想】

归并排序是分治策略的一个非常典型的应用，其基本思想是将 $n$ 个待排序的记录看成是 $n$ 个长度为 $1$ 的有序序列，然后两两进行归并，第一轮得到 $\frac{n}{2}$ 个长度为 $2$ 的有序序列，第二轮得到 $\frac{n}{4}$ 个长度为 $4$ 的有序序列，以此类推，直到得到一个长度为 $n$ 的有序序列

归并排序的核心是归并操作，即将两个已经排序的序列合并成一个序列的操作，其步骤如下：