排序技术

插入排序
基本思想：每次从数列中取出一个未取出的数，按照大小关系插入到已取出的数中，使已取出的数依然有序

插入排序代码

希尔排序
基本思想：先将一个长序列分割为几个短序列进行插入排序，将原始序列排成基本有序的顺序再进行插入排序。

希尔排序代码

冒泡排序
基本思想：核心是交换，对相邻俩个数据进行比较，如果逆序则交换，数次交换后，小的会到队头，大的会到队尾

冒泡排序代码

快速排序
基本思想：使用分治策略把一个序列分成俩个子序列，其中一部分的记录比另一部分小，随后再对这俩部分分别再分成俩部分，使一部分的所有记录比另一部分小，如此反复

快速排序代码

简单选择排序
基本思想：每一趟都在所有记录中选取最小的记录放入有序数列中，如此反复就能将无序序列有序化

选择排序代码

堆排序
基本思想：利用堆的数据结构设计的算法，堆的定义：一颗完全二叉树所有结点（除了叶子结点）的值都小于其左右孩子结点的值，则这棵完全二叉树就被称为堆。
每次将堆的顶点输出，再调整剩余数据使其重新排成一个堆。重复这个过程就能得到一个有序数列

堆排序代码

归并排序
基本思想：非常典型的分治法采用。先将单个序列视为有序序列，然后不断将相邻的俩个有序序列合并得到新的序列，如此反复最终得到一个有序序列

归并排序代码

桶排序
基本思想：基于空间换时间的排序方法。桶排序假设数据服从均匀分布，然后将排序序列划分成若干区间，一个区间看成一个桶，再通过一个映射函数将序列中的记录映射到桶中，再对每个桶中的记录进行排序，然后按序输出

桶排序代码

基数排序
基本思想：通过关键字排序对单逻辑记录进行排序的方法。举个例子，对一副打乱的牌，如何使其再次有序？首先按照牌面的不同记录分成13堆，如何所有同记录的堆到一起，再按顺序叠放

基数排序代码

索引与查找技术

二叉排序树
二叉排序树，也称二叉查找树，它是一颗空树或者是具有下列性质的二叉树：
（1）若左子树不为空，则左子树上所有结点的值均不小于它的根结点的值
（2）若右子树不为空，则右子树上所有结点的值均不大于它的根结点的值
（3）左右子树也分别为二叉排序树
基本思想：在随机遇到一个数据时可以很快的进行插入，并保持二叉树中序遍历有序的状态，这个特质使其非常使用于动态索引
一颗二叉排序树：

二叉排序树代码实现

线性表的查找技术
1.顺序查找
基本思想：从线性表的一端到另一端将关键字与给定的查找值逐个进行比较。若查找成功则返回记录在数据表中的位置；若未找到关键字，则查找失败，返回查找失败信息

顺序查找代码

2.折半查找
类似二分查找，将待比较的key值与第mid=(low+high)/2位置的元素进行比较

折半查找代码

内插查找
基本思想：根据数学上的内插法，当知道关键字K位于K1和Kh之间时将下一次查找的位置选在
（K - K1) / (Kh - K1)这一比例点上

折半查找代码

字典树
专门用于字符串查找而设计的一种排序树。字典树具有以下三个基本性质：
（1）根结点不包含字符，除根结点外每一个结点都只包含一个字符
（2）从根结点到某一结点，将路径上的字符连接起来，为该结点对应的字符串
（3）每个结点的所有子结点包含的字符都不相同

字典树实现代码

散列表
散列表，也称哈希表。根据关键码值而直接访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，加快查找的速度。这个映射函数也叫做散列函数
记录的存储位置=f(关键字)
哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。）
而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

哈希表实现

经典算法

递归
递归的基本思想是把规模大的问题转化为规模小的相似子问题来解决。在函数实现时，因为解决大的问题和解决小的问题的方法往往是同一方法，所以就产生了函数调用它自己的情况。另外，解决问题的函数必须要有递归边界，也就是递归结束的条件，否则将无限递归下去

递归实现整数n的阶乘
递归算法解决汉诺塔问题

迭代
迭代利用计算机运算速度快，适合做重复性操作这一特点，让计算机对一组指令进行重复执行。使用迭代要做好以下三个方面的操作：
（1）确定迭代变量
在可以用迭代解决的问题中，至少存在一个直接或间接的、不断有旧值递推出新值的变量
（2）建立迭代关系式
即如何从变量的前一个值退出其下一个值的公式，可以用递推或者倒推的方法来完成
（3）对迭代过程进行控制
要考虑什么时候结束迭代过程

迭代实现斐波那契数列

贪心算法
贪心算法在对问题求解时不从整体最优上考虑，所做的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，其算法设计的关键是贪心策略的选择。选择的贪心策略必须具备无后效性，即某个状态之后的过程不会影响之前的状态，只与当前状态有关。
要注意贪心算法的适用条件与前提：最优子结构和贪心选择性质
最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，即每一步的最优解可以带来问题的整体最优解
贪心选择性质是贪心算法与动态规划的主要区别，与动态规划相比，虽然贪心算法和动态规划都具有最优子结构性质，但动态规划通常自底向上的方式解决问题，而贪心算法通常一自顶向下的方式进行求解

贪心算法经典问题--活动安排问题

参考文章：

一文搞定十大经典排序算法
图解基数排序
图解桶排序
哈希表（散列表）详解