插入排序

思路:
把集合分成有序表與無序表,最開始有序表只有一個元素,無序表有n-1個元素,排序過程中每次取出無序表的第一個元素,然后與有序表中的元素比較,插入到適當位置
小結:
1.一共要進行n-1次排序循環

排序過程

排序前---
[101, 34, 119, 1]
第1輪插入后---
[34, 101, 119, 1]
第2輪插入后---
[34, 101, 119, 1]
第3輪插入后---
[1, 34, 101, 119]

代碼實現:

public class InsertSort {public static void main(String[] args) {int arr[] = {101, 34, 119, 1};System.out.println("排序前---");System.out.println(Arrays.toString(arr));insertSort(arr);}public static void insertSort(int[] arr) {//因為無序集合的第一個數是arr[1]for (int i = 1; i < arr.length; i++) {//第一輪 34,101,119,1int insertVal = arr[i];//待插入的數(針對無序集合),是無序集合中的第一個arr[1],arr[0]是有序集合的第一個int insertIndex = i-1;//insertval的下標前一個數,要插入的位置//insetVal找到要插入的位置//insertIndex >= 0保證其不要越界//insertVal<arr[insertIndex]待插入的數還沒有找到插入位置,arr[insertIndex]還得向后移//要插入的數得小于要插入下標位置的數while (insertIndex >= 0 && insertVal < arr[insertIndex]) {//arr[insertIndex]向后移arr[insertIndex + 1] = arr[insertIndex];insertIndex--;}//判斷是否需要賦值if (insertIndex+1!=i){//當退出while()時說明,要插入的位置找到:insertIndex+1arr[insertIndex+1]=insertVal;}System.out.println("第"+i+"輪插入后---");System.out.println(Arrays.toString(arr));}}
}

無注釋版:

public class TestSort {public static void main(String[] args) {int arr[] = {101, 34, 119, 1};System.out.println("排序前---");System.out.println(Arrays.toString(arr));insertSort(arr);}public static void insertSort(int[] arr) {for (int i = 1; i <arr.length ; i++) {int value=arr[i];int index=i-1;while (index>=0&&value<arr[index]){arr[index+1]=arr[index];index--;}if (index+1!=i){arr[index+1]=value;}System.out.println("第"+i+"輪插入后---");System.out.println(Arrays.toString(arr));}}
}