InsertionSort

插入排序,感觉挺有意思,可以理解成扑克牌,先取了张12,新取了张15,比12大,放右边;新取了张9,比15小,左移,和15换个位置,比12也小,继续左移

源码

package Love;

/**
* Hello world!
*/

public class App {

public static void insertionSort(int[] arr) {
int len = arr.length;
int preIndex = 0;
int thisNum = 0;
for (int i = 0; i < len - 1; i++) {
preIndex = i;
thisNum = arr[i + 1];

while (preIndex >= 0 && arr[preIndex] > thisNum) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = thisNum;
}
}

public static void main(String[] args) {
int arr[] = {4, 6, 3, 9, 6, 5, 1, 7, 6, 5, 2, 8};
insertionSort(arr);
for(int a : arr){
System.out.print(a + " ");
}

}
}

6比4大,while里不执行,直接arr[1]=6;变成了4 6

3比6小,执行while里的交换,arr[2]=6,preIndex=0;arr[0]=4>3继续成立,执行while里的交换,arr[1]=4,preIndex=-1;接着退出while,arr[0]=3;变成了3 4 6

9比6大,while里不执行,arr[3]=9;变成了3 4 6 9

6比9小,执行while里的交换,arr[4]=9,preIndex=2;arr[2]=6 > 6不成立,因此while结束;arr[3]=6;变成3 4 6 6 9

如此循环最终得到结果

发表评论