Java实现直接插入排序与折半插入排序的示例详解

这篇文章主要为大家详细介绍了插入排序中两个常见的排序：直接插入排序与折半插入排序。本文用Java语言实现了这两个排序算法，感兴趣的可以学习一下

1.直接插入排序

插入排序的基本思想: 主要分为两个区间, 无序区间和有序区间, 每次选择无序区间的第一个元素, 在有序区间内选择合适的位置进行插入操作.

插入过程如下图所示:

代码:

public class InsertSort { public static void insertSort(int[] array) { for (int i = 1; i = 0; j--) { if (array[j] > tmp) { array[j+1] = array[j]; } else { break; } } array[j+1] = tmp; } } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); insertSort(arr); System.out.println(Arrays.toString(arr)); } }

运行结果:

性能分析:

2. 折半插入排序

折半插入的详细过程如下:

代码:

public class InsertSort { public static void bsInsertSort(int[] array) { for (int i = 1; i = array[aver]) { left = aver + 1; } else { right = aver; } } for (int j = i; j > left; j--) { array[j] = array[j-1]; } array[left] = tmp; } } public static void main(String[] args) { int[] arr = {3,2,5,7,1,6,8,9,4}; System.out.println(Arrays.toString(arr)); bsInsertSort(arr); System.out.println(Arrays.toString(arr)); } }

运行结果: