小禹禹，你们好呀，景禹最近着实太忙，但我为了保证质量每天都会将所有空闲时间都用来给大家写文章，希望能我的文章能帮到你，不论是考试还是面试，亦或者是你的教学。今天我们一起来看三款经典的排序算法！
跳跃查找（Jump Search）
与二分查找类似，跳跃查找也是在有序数组上进行的。基本思想是以固定步长向前跳越，从而跳过尽可能多的不在待查找元素附近的元素，减少查找过程中的比较次数。
比如，假设我们有一个大小为 n 的数组 arr[] 和一个步长 m，那么我们仅查找 arr[0],arr[m],arr[2m],...,arr[km] 等等位置。当发现了待查找元素 x 位于区间
, 则在该区间上进行线性查找（Linear Search ） ，继而确定待查找元素是否存在，若存在返回待查找元素 x 的下标；若不存在，则返回 -1。
为了清楚起见，景禹以下面的例子带大家一起 Step By Step。
数组的长度为16，假定我们取步长为
，我们以查找元素88为例进行说明。跳跃查找，总体可以分为两步：第一步确定待查找元素的范围，第二步线性搜索第一步确定的范围。
如何确定待查找元素的范围？
我们设置一个保存待查找范围左区间的指针pre，还有一个进行扫描的指针 step，每次按照步长 4 向前跳跃，具体我们一步一步看一下。
第一步：变量pre 指向下标为0的位置，step 指向数组中下标为4的位置。
第二步：判断 step 指向的元素的前一个元素 21 与待查找元素88的大小，若小于待查找元素，则移动pre指针到step的位置，并将step更新为step加上步长；否则，线性查找 pre指针到 step 指针范围。这里21小于88，则将 pre 更新为4，将step更新为8。
第三步：判断 step指向的元素的前一个元素 75 与 88 的大小，发现小于88，则将 pre 更新为step的值 8，将step的值更新为 step + 步长，即 8+4=12.
第四步：判断 step指向的元素的前一个元素 101 与 88 的大小，发现大于88，故可以确定88在
的范围之内。具体88是否存在，则可以通过线性查找区间
即可。
第五步：线性查找区间
，判断pre指向的元素80与88的大小，发现小于，则将pre指针向前移动到下标9.
第六步：判断pre指向的元素88与待查找元素相等，则返回下标 9 。
实现代码
public class JumpSearch
{
public static int jumpSearch(int[] arr, int x)
{
int n = arr.length;
//将step初始化为步长（根号下数组长度）
int step = (int)Math.floor(Math.sqrt(n));
//将prev初始化为0
int prev = 0;
//确定待查找元素所在范围
while (arr[Math.min(step, n)-1] < x)
{
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
//从pre==8开始线性查找元素88
while (arr[prev] < x)
{
prev++;
//如果到达了step或者数组的末尾都没找到，则返回-1.
if (prev == Math.min(step, n))
return -1;
}
//如果相等则找到了待查找元素。
if (arr[prev] == x)
return prev;
return -1;
}
public static void main(String [ ] args)
{
int arr[] = { 5, 13, 19, 21, 37, 56, 64, 75, 80,
88, 92, 101, 156, 218, 315, 458};
int x = 88;
int index = jumpSearch(arr, x);
System.out.println("\nNumber " + x +
" is at index " + index);
}
}
时间复杂度分析
对于一个包含n的元素的有序数组，最坏的情况下，需要进行
次跳跃且最后一个元素的值大于待查找元素，则还需要进行线性查找，进行m-1比较。因此，跳跃查找最坏情况下执行
次，当
时，
取得最小值，也就意味着时间复杂度最低，最好的步长为
。跳跃查找的时间复杂度则为
量级。
跳跃查找小结
跳跃查找与二分查找一样都是在有序数组上进行的；
跳跃查找的最佳步长
。
跳跃的时间复杂度
介于线性查找的时间复杂度
和二分查找
之间。
二分查找比跳跃查找的时间复杂度更低，但是跳跃查找的优势在于仅需要回溯一次（即线性遍历的部分），而在搜索数组中最小的元素或者最大元素的情况下，二分查找需要回溯多次。因此，在二分查找成本很高的时候，我们可以考虑跳跃查找。
插值查找(Interpolation Search)
给定一个包含 n 个元素且 均匀分布 的有序数组 arr[]，查找该数组中的某个特定元素 x 就可以考虑插值查找。线性查找（Linear Search）时间复杂度为
，跳跃查找（Jump Search）为
，二分查找为
.
对于一个 均匀分布 的有序数组而言， 插值查找是对于二分查找的改进。二分查找总是对于一个查找区间的中间值进行检查，而插值查找则没有这个局限性，插值查找根据要查找的值确定查找的位置，比如查找靠近有序数组最末尾的元素时，插值查找倾向于直接从有序数组的末端进行查找，而不会像二分查找，每一次都查找查找区间内的中间元素，然后不断缩减查找区间，直到靠近有序数组的末尾。
二分查找中求 mid 索引的公式为：
插值查找求 mid 索引的公式为：
至于这个计算公式的有效性证明景禹就不装大尾巴了，感兴趣的小禹禹可以后台回复 “插值查找” 获取论文下载链接，自行研究。小禹禹对这个公式也可以简单理解为，当查找的元素靠近 arr[high] 时，这个公式计算出来的 mid 也靠近 high；当查找的元素靠近 arr[low] 时，公式计算出的 mid 就靠近 low 。
那我们以下面的例子一起愉快地开始学习算法本身的执行过程吧。我们以查找元素18为例进行说明。
第一步：计算mid，low 等于0，high等于14，arr[low]为10，arr[14]为47，
.
第二步：将mid指向的元素16与待查找元素18比较，发现小于18，则将low更新为mid+1，即为4的位置。这一步骤和二分查找是一样的。
第三步，重新计算mid，
转播
