插入排序

插入排序

插入排序的思路：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在前面已排序的元素序列中，从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

https://lixj.fun/upload/2021/07/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F-ccfb2330d0bf4e04afd9e840b4e99bbc.gif

平均时间复杂度：O(n²)

空间复杂度：O(1)

算法稳定性：稳定

public class InsertSort3 {
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            while (j > 0 && arr[j-1] > temp) {
                arr[j] = arr[j-1];
                j--;
            }
            if (i != j) {
                arr[j] = temp;
            }
        }

    }


    public static void main(String[] args) {
        int a[] = new int[]{32, 43, 23, 13, 5};
        insertSort(a);
        for (int i=0; i<a.length; i++) {
            System.out.print(a[i] + ",");
        }
    }
}

复制

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可 Links:https://lixj.fun/archives/插入排序