排序算法图解之Java插入排序

时间:2022-11-07 兴趣使然黄小黄人气:0

1.插入排序简介

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

2.插入排序思想及图解

插入排序的基本思想如下：

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

以序列：{55, 85, 21, 12, 5} 为例，图解如下：

粉红色部分为每轮认定的有序部分，其余颜色为认定的无序部分。绿色标识为每轮遍历的无序序列的位置，将该位置的元素逐一与有序部分进行比较，找到合适的位置进行顺序表的插入操作。

3.插入排序代码实现

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 插入排序
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] array = {55, 85, 21, 12, 5};
        System.out.println("排序前: " + Arrays.toString(array));
        insertSort(array);
        System.out.println("排序后: " + Arrays.toString(array));
    }

    //插入排序
    public static void insertSort(int[] arr){
        //边界条件
        if (arr.length < 1){
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            //定义待插入的位置和待插入的数
            int insertIndex = i-1; //arr[i]前面的位置,便于插入
            int insertVal = arr[i]; //先将待插入的值保存
            //给insertVal找到待插入的位置
            //1.insertIndex > 0防止越界
            //2.insertVal < arr[insertIndex] 说明还未找到待插入的位置
            while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex != i){
                arr[insertIndex+1] = insertVal; //插入
            }
            System.out.println("第" + i + "轮: " + Arrays.toString(arr));
        }
    }
}

加载全部内容