【排序知多少】插入排序详解
2020-01-08 本文已影响0人
齐鑫
插入排序思路
1、从待排序元素中的第二个元素开始进行遍历
2、记录当前元素作为临时变量
3、判断当前元素前的元素是否小于当前元素,小于则不处理,否则把当前元素和前一元素进行互换
4、进行遍历,直到当前元素前的所有元素都已经排好序为止
插入排序理解
插入排序就是从数组的开始两个数进行排序,排好之后再对第三个数进行排序,直到对所有的元素全部进行排序之后,完成排序的逻辑。每次排序的过程,就是要当前确认当前元素在需要排序的所有元素中的位置,如果位置正确(即已经是有序的),则只需要进行判断,不需要插入元素,否则需要把元素插入到对应的位置中。
插入排序复杂度
插入排序要进行两层遍历,第一层是对所有元素进行遍历,第二层是在第一层遍历过程中,对当前元素前的元素进行遍历,所以插入排序的复杂度是O(n^2)。
插入排序JAVA代码实现
public class Main {
public static void main(String[] args) {
int[] arr = {3, 2, 4, 1, 5};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 插入排序:
* 1、从待排序元素中的第二个元素开始进行遍历
* 2、记录当前元素作为临时变量
* 3、判断当前元素前的元素是否小于当前元素,小于则不处理,否则把当前元素和前一元素进行互换
* 4、进行遍历,直到当前元素前的所有元素都已经排好序为止
*
* @param arr
*/
private static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int leftindex = i - 1;
while (leftindex >= 0 && arr[leftindex] > temp) {
arr[leftindex + 1] = arr[leftindex];
leftindex--;
}
arr[leftindex + 1] = temp;
}
}
}