:-: 14.5 折半插入排序 * * * * * **基本概念：** 它是一种简单直观的排序算法（插入排序的一个变种）。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中采用了折半查找（也称二分查找），找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 二分查找法：是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 **算法的运作：** 1、将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2、从头（第二个元素开始）到尾依次扫描未排序序列，将扫描到的元素（待插入元素）与在已排序序列中采用折半查找（先与已排序序列中的中间元素做对比，如果大于（小于），就与右（左）边的一半的中间元素继续做对比，重复以上查找步骤，直到寻找到合适的位置），如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。或者待插入的元素大于有序序列中的某个元素且小于此元素的后一个元素，则将待插入元素插入到此元素的后面。 **图片示例：** :-:  **代码实现：** ~~~ public void binaryInsertionSort(int nums[]) { for (int i = 1; i < nums.length; i++) { int low = 0; int high = i - 1; int temp = nums[i]; while (high >= low) { int mid = (high + low) / 2; if (nums[mid] > temp) { high = mid - 1; } else { low = mid + 1; } } for (int j = i; j > low; j--) { nums[j] = nums[j - 1]; } nums[low] = temp; } } ~~~ **复杂度分析：** 时间复杂度：平均：O(n^2)、最坏：O(n^2)、最优：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。** **本文主要参考以下文章：** [折半插入排序算法详解（示例图片来源）](https://blog.csdn.net/guoweimelon/article/details/50904206)