七大排序之插入排序

---

插入排序

插入排序：插入排序是一种原址（in-place）排序，原址的意思就是对于任何的输入数据序列都可以在不占用或者只占用常量的额外存储空间的情况下完成排序。插入排序对于已经排序好的数据可以实现O(n)的最佳排序时间，对于逆序的数据序列排序运行时间最差O(n^2)。

排序算法的稳定性：通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同，即相对位置保持不变。
插入排序是一个稳定的排序算法！

插入排序过程：

• 将集合分为两个区间，i 为当前遍历元素
• 已经排序的区间 [0,i) ，待排序的区间 [i,n]
• 每次从待排序区间中将第一个元素“插入”到已排序区间的合适位置，直到整个数据有序

直接插入排序

代码如下：

 public static void insertionSort(int[] arr){
        //1.[i,arr.length]未排序区间，i为当前遍历元素
        for (int i = 1; i <arr.length ; i++) {
            //2.[0,j)已排序区间，j-1是已排序区间的最后一个元素
            for (int j = i; j >0 ; j--) {
                //3.等于时也不交换，保证排序的稳定性
                if (arr[j]>=arr[j-1]){
                    break;
                }
                swap(arr,j,j-1);
            }
//            for (int j = i; j>0 && arr[j]
//                swap(arr,j,j-1);
//            }
        }
    }
    public 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
13
14
15
16
17
18
19
20
21

折半插入排序

折半插入排序是利用二分查找来定位元素的插入位置：

public static void insertionSortBS(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int val=arr[i];
            int left=0;
            int right=i;
            //对已排序区间进行二分查找
            while (left<right){
                int mid=left+(right-left)/2;
                if (val>=arr[mid]){
                    left=mid+1;
                }else{
                    right = mid;
                }
            }
            //搬移元素
            for (int j = i; j >left ; j--) {
                arr[j]=arr[j-1];
            }
            //此时left的位置就是要插入的位置
            arr[left]=val;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

希尔排序

希尔排序：缩小增量排序
每次取一个整数gap（gap一般都选取数组长度的一半或者三分之一），将原数组按照gap分组，组内使用插入排序，直到 gap=1 时，整个数组已经接近有序，最终直接插入排序一下即可。希尔排序时间复杂度为O(n^1.3-1.5)。
希尔排序是一个不稳定的排序算法！！！

代码如下：

public static void shellSort(int[] arr){
        //1.计算gap
        int gap=arr.length/2;
        while (gap>1){
            //2.gap数组内部进行插入排序
            insertionSortByGap(arr,gap);
            gap/=2;
        }
        //3.此时数组已经接近有序，使用插入排序进行最后排序
        insertionSort(arr);
    }
    public static void insertionSortByGap(int[] arr,int gap){
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j-gap>=0 ; j-=gap) {
                if (arr[j]<arr[j-gap]){
                    swap(arr,j,j-gap);
                }else{
                    break;
                }
            }
        }
    }
    public static void insertionSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j]>=arr[j-1]){
                    break;
                }else{
                    swap(arr,j,j-1);
                }
            }
        }
    }
    public 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
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

总结

以上就是今天要讲的内容，本文介绍了插入排序和希尔排序，插入排序包括直接插入排序和折半插入排序，而希尔排序就是利用插入排序来完成排序的，所以它也算是一种插入排序。如果你觉得有收获的话，就留下你的👍吧！