yishujixiaoxiao 2019-12-23
package algorithm.sort; import java.util.Arrays; /** * 直接插入排序 * 算法思想:将一个记录插入到已排好序的序列中,从而得到一个新的有序序列(将序列的第一个数据看成 * 是一个有序的子序列,然后从第二个记录逐个向该有序的子序列进行有序的插入,直至整个序列有序) * @author camus * */ public class DirectInsertSort { public static void main(String[] args) { int[] arr = {16,6,3,4,12,8,1,9,2}; //16 6 3 4 12 8 1 9 2 //1、6 16 3 4 12 8 1 9 2 i=1,6与16比较,结果 6 16 //2、3 6 16 4 12 8 1 9 2 i=2,3与16比较,再与6比较,结果3 6 16 //3、3 4 6 16 12 8 1 9 2 i=3,3 4 6 16 //4、3 4 6 12 16 8 1 9 2 //5、3 4 6 8 12 16 1 9 2 //6、1 3 4 6 8 12 16 9 2 //7、1 3 4 6 8 9 12 16 2 //8、1 2 3 4 6 8 9 12 16 int temp; for (int i=1;i<arr.length;i++){ //待排元素小于有序序列的最后一个元素时,向前插入 if (arr[i]<arr[i-1]){ temp = arr[i]; for (int j=i;j>=0;j--){ if (j>0 && arr[j-1]>temp) { arr[j]=arr[j-1];//小的值向前插入 }else { arr[j]=temp; break; } } } } System.out.println(Arrays.toString(arr)); } }