算法

【排序知多少】插入排序详解

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;
        }
    }
}
上一篇下一篇

猜你喜欢

热点阅读