快捷導(dǎo)航

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

更新時(shí)間：2022年11月06日 09:01:00 作者：興趣使然黃小黃

插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增1的有序表。本文通過圖片合示例講解了插入排序的實(shí)現(xiàn)，需要的可以了解一下

1.插入排序簡(jiǎn)介

插入排序，一般也被稱為直接插入排序。對(duì)于少量元素的排序，它是一個(gè)有效的算法。插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng)

2.插入排序思想及圖解

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

把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表，開始時(shí)有序表中只包含一個(gè)元素，無(wú)序表中包含n-1個(gè)元素，排序過程中每次從無(wú)序表中取出第一個(gè)元素，把它的排序碼依次與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中的適當(dāng)位置，使之成為一個(gè)新的有序表。

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

粉紅色部分為每輪認(rèn)定的有序部分，其余顏色為認(rèn)定的無(wú)序部分。綠色標(biāo)識(shí)為每輪遍歷的無(wú)序序列的位置，將該位置的元素逐一與有序部分進(jìn)行比較，找到合適的位置進(jìn)行順序表的插入操作。

3.插入排序代碼實(shí)現(xiàn)

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++) {
            //定義待插入的位置和待插入的數(shù)
            int insertIndex = i-1; //arr[i]前面的位置,便于插入
            int insertVal = arr[i]; //先將待插入的值保存
            //給insertVal找到待插入的位置
            //1.insertIndex > 0防止越界
            //2.insertVal < arr[insertIndex] 說(shuō)明還未找到待插入的位置
            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));
        }
    }
}