数据结构与算法-实战(7)

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秒（比选择排序更快）
    }
}