实例 | Java 折半插入排序算法及解析

vlambda
2020-02-25

实例 | Java 折半插入排序算法及解析

关注新技术，学习新知识！

折半插入排序是直接插入排序与折半查找二者的结合，仍然是将待排序元素插入到前面的有序序列，插入方式也是由后往前插，只不过直接插入排序是边比较边移位。而折半插入排序则是先通过折半查找找到位置后再一并移位，最终将待排序元素赋值到空出位置。

执行结果和解析过程：

代码如下：（请点击下面“阅读原文”，可在线编辑运行查看结果）

/** * 折半插入排序 的实现 稳定算法 * nowjava.com */public class InsertSort { public static void main(String[] args) { // TODO Auto-generated method stub int a[] = { 3, 1, 5, 7, 2, 4, 9, 6 }; new InsertSort().doInsertSort(a); }
 /** * 折半插入排序算法的实现 */ private void doInsertSort(int[] a) { // TODO Auto-generated method stub System.out.println("—————折半插入排序算法—————"); int n = a.length; int i, j; for (i = 1; i < n; i++) { /** * temp为本次循环待插入有序列表中的数 - nowjava.com */ int temp = a[i]; int low = 0; int high = i - 1; /** * 寻找temp插入有序列表的正确位置，使用二分查找法 */ while (low <= high) { /** * 有序数组的中间坐标，此时用于二分查找，减少查找次数 */ int mid = (low + high) / 2; /** * 若有序数组的中间元素大于待排序元素，则有序序列向中间元素之前搜索，否则向后搜索 */ if (a[mid] > temp) { high = mid - 1; } else { low = mid + 1; } }
 for (j = i - 1; j >= low; j--) { /** * 元素后移，为插入temp做准备 */ a[j + 1] = a[j]; } /** * 插入temp */ a[low] = temp; /** * 打印每次循环的结果 */ print(a, n, i); } /** * 打印排序结果 */ printResult(a, n); }
 /** * 打印排序的最终结果 *  * @param a * @param n */ private void printResult(int[] a, int n) { System.out.print("最终排序结果："); for (int j = 0; j < n; j++) { System.out.print(" " + a[j]); } System.out.println(); }
 /** * 打印排序的每次循环的结果 *  * @param a * @param n * @param i */ private void print(int[] a, int n, int i) { // TODO Auto-generated method stub System.out.print("第" + i + "次："); for (int j = 0; j < n; j++) { System.out.print(" " + a[j]); } System.out.println(); }}