【概述】

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

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

无论什么时候，每当想起自己曾满怀激情、兴奋、惊奇与真诚等等情绪，在键盘上敲出的第一个程序——“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$ 的有序序列

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

【基本思想】

快速排序对冒泡排序的一种改进，在冒泡排序中，记录的比较与移动是在相邻位置进行的，记录每次交换只能后移一个位置，因而总的比较次数与移动次数较多；而在快速排序中，记录的比较与移动是从两端向中间进行的，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面移动到前面，由于记录移动的距离较远，从而减少了总的比较次数与移动次数

快速排序利用了分治策略，其基本思想是：首先选一个轴值，作为比较的基准，将待排序记录划分为独立的两部分，左侧记录均小于等于轴值，右侧记录均大于等于轴值，然后分别对这两部分重复上述过程，直至序列有序

【基本思想】

鸡尾酒排序也称双向冒泡排序、定向冒泡排序，是原始冒泡排序的改进

双向冒泡排序与冒泡排序的不同在于其从低到高比较，然后再从高到低比较，如此循环往复，直到序列有序，而冒泡排序仅是从低到高的去比较序列中的每个元素

【基本思想】

原始冒泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的关键码，若反序则交换，直到没有反序为止

原始冒泡排序的具体的排序过程如下：