1. 插入排序

• 什么是插入排序？
  插入排序（Insertion-Sort）：是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

1.2 时空复杂度

• 时间复杂度：O(n²) 最好O(n²) 最坏O(n)
• 空间复杂度：O(1)
• 稳定性：稳定（相同元素排序后相对位置不发生交换）

1.3 动图演示

1.4 算法实现

• 移动法

public class insertSort {
    public static void main(String[] args) {
        int[] num = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48} ;
        int j;
        //i=1；从1开始，没必要和自己比
        for (int i = 1; i < num.length ; i++) {
            //记录要插入的值，这时就有了一个长度为i+1的数组可以进行移动
            int temp = num[i];
            System.out.print("第"+i+"次移动的位置：");
            //在已排序的数组中找到比记录值（temp）要小的值，位置往后移动（记住此时的数组长度（i+1））
            //要明白为什么往后移动。
            //j >= 0&&num[j] > temp要满足这两个条件，j才会j--；
            for (j = i - 1;j >= 0&&num[j] > temp ;j--)
            {
                System.out.print(j+" ");
                //符合条件的往后移动一位
                num[j + 1] = num[j];
            }
            System.out.println("\n第"+i+"次移动后的数组："+Arrays.toString(num)+"，此时j+1的位置为："+(j+1));
            //归位，此时符合条件的都全部移动了一位，此时的j+1就是记录值要插入的位置
            num[j + 1] = temp;
            System.out.println("第"+i+"次交换后的结果："+Arrays.toString(num));
        }
        System.out.println("最终的排序结果："+Arrays.toString(num));
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 交换法

public static void insertSort(int[] arr){
    for(int i = 0; i < arr.length; i++){
        for(int j = i; j>=0&&arr[j]<arr[j-1];j--){
            swap(arr,j,j-1);
        }
    }
}
private static void swap(int[] arr,int i,int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12

2. 总结

稳定的排序算法。插入排序相当于从第一个元素开始，将后面的元素一个个往进插，新插的元素一个一个与前面的比较，遇到比自己大的交换，遇到比自己小的则插入这个位置。所以左边的元素永远是有序的

活动地址：CSDN21天学习挑战赛

---

每一个你不满意的当下，都有一个你不曾努力的过去。