GitHub Viewer
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 = arr[mid]) {
//这里包括了等于的情况--->如果等于，角标+1，那么则是直接插入
left = mid + 1;
} else {
//比中间数小的，往左边找
right = mid - 1;
}
}
//角标相撞了才结束循环..
return left;
}
}