常见排序算法之插入排序

电玩女神 2024-04-18 17:07 65阅读 0赞

# 插入排序 #

欢迎来我个人博客：[原文地址][Link 1]

### 原理： ###

（此部分全靠自己理解编写，与百度百科中的直接插入有所不同，如有错误，欢迎联系我指正批评）

把数组分为有序部分与无序部分，当一个数组排序时，第\[0\]位置上为有序部分，其余部分为无序部分，详细见下面图解。然后让无序部分插叙有序部分，先让有序部分最后一个与无序部分第一个比较，如果条件满足（大，或者小）就交换位置，然后依次与有序部分倒数第二个继续比较，直到不需要交换位置。这样组成了新的有序部分与部分，然后重复前面步骤。

### 图解： ###

![\{%asset\_img 插入排序01.png%\}][asset_img _01.png]

### 代码实现： ###

public class InsertionSort {
    
        public static void main(String[] args) {
            int[] arr = {9, 3, 6, 0, 1, 4, 2, 7, 5, 8};
            System.out.println("排序前：");
            System.out.println(Arrays.toString(arr));
            insertonSort(arr);
            System.out.println("排序后：");
            System.out.println(Arrays.toString(arr));
        }
    
        private static void insertonSort(int[] arr) {
    
            //第i词插入
            for (int i = 1; i < arr.length; i++) {
    
                //无序部分第一个值，即待插入值
                int value = arr[i];
                //有序部分最后一个值
                int yw = i - 1;
                //插入位置结束条件
                while (yw >= 0 && arr[yw] > value) {
    
                    //待插入值先前移动，有序部分向后移动
                    arr[yw + 1] = arr[yw];
                    //让待插入值与有序部分倒数第（yw+） 比较
                    yw--;
                }
                //待插入值插入,因为退出循环，说明位置找到（yw+1）
                arr[yw + 1] = value;
    
            }
    
        }
    }

排序前：  
\[9, 3, 6, 0, 1, 4, 2, 7, 5, 8\]  
排序后：  
\[0, 1, 2, 3, 4, 5, 6, 7, 8, 9\]

[Link 1]: http://blog.bubbletg.cn/2019/02/03/%E5%B8%B8%E8%A7%81%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%B9%8B%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/
[asset_img _01.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c280de0f35cd4dde83d2d8c0175f960e.png