package sort; /** * Created by ozc on 2018/3/15. * * @author ozc * @version 1.0 */ public class InsertSort { public static void main(String[] args) { int[] arrays = {9, 8, 1, 4, 2, 3, 5, 6, 7, 13, 12, 14, 11, 15, 16, 17, 19, 18, 10}; sort2(arrays); System.out.println(arrays); } /** * 插入排序普通版 * @param arrays */ public static void sort(int[] arrays) { //int[] arrays = {3, 2, 1, 3, 3}; /* //第一趟排序-------------------- int temp; if (arrays[1] > arrays[0]) { //如果第二个数比第一个数大，直接跟上 } else { //如果第二个数比第一个数小，将第一个数后退一个位置(将第二个数插进去) temp = arrays[1]; arrays[1] = arrays[0]; arrays[0] = temp; } System.out.println("公众号Java3y" + arrays); //第二趟排序-------------------- if (arrays[2] > arrays[1]) { //如果第三个数比第二个数大，直接跟上 } else { //如果第三个数比第二个数小，将第二个数往后退一个位置，让第三个数跟第一个数比 temp = arrays[2]; arrays[2] = arrays[1]; //如果第三个数比第一个大，那就插入到第二个数中 if (temp > arrays[0]) { arrays[1] = temp; } else { //如果第三个数比第一个小，将第三个数插入到第一个数前面 int swapTemp = arrays[0]; arrays[0] = temp; arrays[1] = swapTemp; } } System.out.println("公众号Java3y" + arrays);*/ //临时变量 int temp; //外层循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据) for (int i = 1; i < arrays.length; i++) { temp = arrays[i]; //如果前一位(已排序的数据)比当前数据要大，那么就进入循环比较[参考第二趟排序] int j = i - 1; while (j >= 0 && arrays[j] > temp) { //往后退一个位置，让当前数据与之前前位进行比较 arrays[j + 1] = arrays[j]; //不断往前，直到退出循环 j--; } //退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中 arrays[j + 1] = temp; } System.out.println("公众号Java3y" + arrays); } /** * 二分插入排序:插入到有序的位置时，使用二分法查找出对应的index，避免多次移动 * @param arrays */ public static void sort2(int[] arrays) { //临时变量 int temp; //外层循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据) for (int i = 1; i < arrays.length; i++) { //二分查找找出合适的插入位置 int index = BinarySearchIndex(arrays, i - 1, arrays[i]); //如果不是直接插入，那么就要移动位置了 if (index != i) { temp = arrays[i]; int j; // 后移元素，腾出arr[index]位置 for (j = i - 1; j >= index && j >= 0; j--) { arrays[j + 1] = arrays[j]; } arrays[j + 1] = temp; } } System.out.println("公众号Java3y" + arrays); } private static int BinarySearchIndex(int[] arr, int maxIndex, int data) { //定义三个指针，分别为待查找区域的两端和中心位置，这个对应的是有序区的大小，不是 整个数组 int left = 0; int right = maxIndex; int mid; //只要左边和右边指针没相撞，那么就可以找 while (left <= right) { //取中间数 mid = (left + right) / 2; //比中间数大的或者等于中间数，往右边找 if (data >= arr[mid]) { //这里包括了等于的情况--->如果等于，角标+1，那么则是直接插入 left = mid + 1; } else { //比中间数小的，往左边找 right = mid - 1; } } //角标相撞了才结束循环.. return left; } }