java算法排序之插入排序

package 十大排序; public class 插入排序 { /* 时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：稳定 */ public static void main(String[] args) { int [] arr ={1,8,6,7,4,5,3,2,9}; sort(arr); } private static void sort(int [] arr ){ if(arr == null || arr.length == 0) return; int curEle, preIndex; // 记录当前待排序元素和前一个元素的下标 for(int i = 0; i < arr.length; i++) { preIndex = i - 1; curEle = arr[i]; //判断前一个元素大于等于零并且前一个元素大于当前的元素 //前面大于当前元素,就让前面大的后移 while(preIndex >=0 && arr[preIndex] > curEle){ arr[preIndex + 1] = arr[preIndex]; // 移动元素 preIndex--; } // 将待排序元素插入新的位置 System.out.println("新的位置:"); System.out.println(preIndex +1); arr[preIndex + 1] = curEle; } } }