07、数据结构与算法 - 实战:排序算法之插入排序

1、基本思想

把n个待排序的元素看成一个有序表和一个无序表,开始时有序表只有一个元素(第一个),无序表中包含 n - 1 个元素(1,2,…,n-1),排序过程每次从无序表取出第一个元素,把它的值依次和有序表的元素进行比较,将它插入到有序表合适的位置,使之成为新的有序表。

2、图解

 

3、代码实现

package cn.klb.datastructures.sort;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description: 实现数组的插入排序
 * @Date: Create in 2023/4/3 23:33
 * @Modified By:
 */
public class Insert {
   
     
    /**
     * 插入排序
     *
     * @param arr
     */
    public static void sort(int[] arr) {
   
     
        int insertVal = 0;  // 保存待插入元素的值
        int insertIndex = 0;    // 保存待插入元素的索引

        for (int i = 1; i < arr.length; i++) {
   
     
            insertVal = arr[i]; // 先把待插入的值保存起来
            insertIndex = i - 1;    // 先假设要插在有序表最后一个位置

            // 判断:
            // 1.待插入的值比待插入位置的值小,则继续往前看有没有更小,直到找不到更小的,就确定了待插入位置
            // 2.当 insertIndex 为0,表示找到尽头了,有序表所有值都比待插入值大,直接插入到最前面
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
   
     
                // 待插入位置的值往后走,腾出位置
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            // 如果待插入位置和预设的一样,就省的换位置了
            if (insertIndex != i - 1) {
   
     
                arr[insertIndex + 1] = insertVal;
            }
        }
    }
}

4、时间复杂度

通过代码可以看出,总共一个for循环,里面嵌套一个while循环。
假设比较次数为C,交换次数为S。
一般情况下,对于内循环while中元素的比较次数C对于 insertIndex 的每个值最多是 insertIndex+1 次,因此对所有的 insertIndex 求和得到总数为 2+3+…+n=O(n²)。
最好的情况下,序列已经是从小到大有序。这时,内循环每次比较都不满足条件,不会进行交换,于是运行次数为 1+1+,…,+n = O(n)。
最坏的情况下,序列从大到小排列。这时,运行次数就直接满足一般情况下的“最多”,为O(n²)。
时间复杂度都是看最复杂的,因此,选择排序的时间复杂度为O(n²)。
可以看出,如果待排序序列几乎被排序,那么插入排序的效率会很好。反之,会很低效。由于这种变化差别很大,因此值得去分析该算法的平均情形的行为,但实际上,插入排序的平均情形时间复杂度也是O(n²)。
首先要明白一点,平均时间复杂度不是最好情况和最坏情况加起来除以二。
以一个数字序列为例,首先要明白一个概念“逆序”,所谓逆序指的是具有性质 i<j 但a[i]>a[j] 的序偶(a[i],a[j])。比如一个序列是{34,8,64,51,32,21},对每一个元素找出序偶,分别是:(34,8)、(34,31)、(34,21)、(64,51)、(64,32)、(64,21)、(51,31)、(51,21)以及(32,21)总共9个逆序。这正式需要由插入排序隐含的执行的交换次数,交换一次两个不按顺序排列的相邻元素恰好消除一个逆序,然后一个排过序的数组没有逆序。
由于算法有除了交换以外的O(N)其他操作(包括比较)。因此插入排序的运行时间是O(I+N),其中I为逆序数。于是,若逆序数为O(N),则插入排序以线性时间运行。
假设有一个包含n个整数的数组,这个数组不存在重复元素,数组的数据是前n个整数的某个排列。那么这个数组的平均逆序数为 n(n-1)/4 。(证明过程可百度查询)
通过交换相邻元素进行排序的任何算法的平均时间复杂度都为O(n²)。(证明过程可百度查询)

5、稳定性

通过代码分析可知,无序列表是从后向前跟有序列表一一对比找出可插入位置,所以当存在两个相同数字,根据本例的代码,其前后相对位置是不会改变的,因此是稳定的。
但是, 当找出可插入位置是逻辑是对有序列表从前向后扫描,那就会破坏两个相同数字的前后关系,导致不稳定。
需要注意的是,排序算法是否为稳定的是由具体算法决定的,不稳定的算法在某种条件下可以变为稳定的算法,而稳定的算法在某种条件下也可以变为不稳定的算法。
总结:插入排序是稳定的。

6、测试

package cn.klb.test.datastructurestest;

import cn.klb.datastructures.sort.*;
import org.junit.Test;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description: 排序测试
 * @Date: Create in 2023/4/3 21:32
 * @Modified By:
 */
public class SotrTest {
   
     
    @Test
    public void testInsert() {
   
     
        int[] arr = new int[800000];
        for (int i = 0; i < 800000; i++) {
   
     
            arr[i] = (int) (Math.random() * 800000);
        }
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Date date1 = new Date();
        System.out.println("-----" + sdf.format(date1) + "-----");

        Insert.sort(arr);

        Date date2 = new Date();
        System.out.println("-----" + sdf.format(date2) + "-----");

        // 80万的随机数据进行插入排序,我的电脑花了大约54秒(比选择排序更快)
    }
}