插入排序（Insert Sort）
直接插入排序的基本操作是將一個(gè)記錄插入到已經(jīng)排好的有序表中溺森，從而得到一個(gè)新的挺物、記錄數(shù)增1的有序表，類(lèi)似打撲克牌排列表蹬敲。
時(shí)間復(fù)雜度：
1）最好情況o(n)
2）最壞情況o(n2/4)
插入排序比選擇排序及冒泡排序性能好些
Paste_Image.png
static void insertSort(int[] array) {
if (array != null && array.length > 0) {
int i, j, key;
for (i = 1; i < array.length; i++) {
key = array[i];
j = i - 1;
while (j >= 0 && key < array[j]) {
array[j + 1] = array[j];//// 如果要插入的元素小于第j個(gè)元素,就將第j個(gè)元素向后移動(dòng)
j--;
}
array[j + 1] = key;// 直到要插入的元素不小于第j個(gè)元素,將insertNote插入到數(shù)組中
}
}
}```
/**
- 將數(shù)組的2個(gè)位置交換
*/
static void swap(int[] array, int i, int j) {
if (array != null && array.length > 0) {
if (i >= 0 && j >= 0 && i <= array.length && j <= array.length) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}```
