🟡前言

21天挑战赛第四天，本文将讲述有关插入排序的知识

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

🟡概述

1️⃣排序原理

1.将元素分为已排序的和未排序的两组

2.找到未排序组中的第一个元素，插入已排序的组中

3.倒序遍历已排序元素，并依次比较

4.当找到比该元素小或者等于该元素的元素时，插入

5.将其余元素向后移动一位

2️⃣原理图

🟡调用API解决

1️⃣构造方法和成员方法

构造方法

Insertion()

成员方法

• public static void sort(Comparable[]a)：对数组a中元素进行排序

• public static boolean greater(Comparable x, Cpmparable y)：判断x是否大于y；

一般使用时会这么写：x.compareTo(y) ，再判断值是否 >0 , >0则表示 x>y

• public static void exch(Comparable[]a, int i, int j)：交换数组a中下标为 i 和 j 的元素

2️⃣解题思路

1.想要对数组内元素进行排序，就要调用 public static void sort(Comparable[]a)

2.排序时从第二个元素开始，依次将后面的每个元素进行排序，所以要调用一个for循环语句来执行，终止条件就是最后一个元素，即 i < a.length

3.每个元素要比较的是它之前的已排序的元素，并判断大小，所以再定义一个元素 j，从已排序组内从后往前比较；

例如当 i = 5 的时候，其实是第6个位置，而 j = 5 的时候，由于从第一个开始计数，所以就表示第五个位置，恰好满足已排序组内的最后一个，终止值就是元素第一个

4.当前一个元素更小时，交换两者；由于比较的是已排序好的元素，所以当碰到前者更小的时候就不用比较，直接退出循环

5.转换成字符串类型后打印输出

3️⃣代码实现

public class InsertionSort {
    public static void sort(Comparable[] a) {
        for(int i = 1; i < a.length; i++){
            for(int j = i; j > 0; j--){
                if(greater(a[j-1], a[j])){
                    exch(a,j,j-1);
                }
            }
        }
    }
    private static boolean greater(Comparable x, Comparable y){
        return x.compareTo(y) > 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

import java.util.Arrays;
public class InsertionSortTest {
    public static void main(String[] args) {
        Integer[] arr = {4,3,2,10,12,1,5,6};
        BubbleSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

🟡时间复杂度

比较元素：(n-1) + (n-2) + … + 2 + 1 = 1/2 * (n^2 - n)

交换元素：(n-1) + (n-2) + … + 2 + 1 = 1/2 * (n^2 - n)

总计：n^2 - n

时间复杂度为：O(n^2)

🟡结语

插入排序也较简单基础，接下来会介绍高级排序