插入排序

>> 饿了么、美团外卖红包领取地址<<

/**
 * 插入排序
 */
@Service
public class InsertionSort implements Sort {

    @Override
    public String getName() {
        return "插入排序";
    }

    @Override
    public int[] sortArray(int[] nums) {
        int t;
        for (int i = 1; i < nums.length; i++) {
            //先将待处理元素保存到临时变量
            t = nums[i];
            //从i的前一个元素开始往前找
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] > t) {
                    //元素比t大,后移
                    nums[j + 1] = nums[j];
                } else {
                    //元素比t小或等于,则j+1的位置为t应该存在的位置,并结束循环
                    nums[j + 1] = t;
                    break;
                }
            }
        }
        return nums;
    }

}

解释:
插入排序有一个很形象的比喻,那就是打扑克牌,在打扑克牌对牌整理的时候,其实就是一个插入排序。左手是整理好的扑克牌,右手一次取一张牌,将右手的牌按照大小顺序插入到左手中正确的位置,这就是插入排序。
实际在代码实现中,因为插入操作对数组来说,就会带来插入位置后面数据的后移操作,所以需要额外处理下,具体逻辑参见代码。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

维特丝(vetes)泡沫发蜡喷雾干胶定型弹力素羊毛卷男女保湿蓬松发胶 泡沫发蜡450ml+旅行装99ml
¥34.00
维特丝(vetes)一梳黑染发剂染发梳植物潮色显白遮盖白发自然清水纯黑发焗油男女梳炫彩 自然黑LW00
¥49.00
维特丝(vetes)染发笔遮白补染快速染发天然植物一次性染发棒 一次性染发棒黑色
¥46.00
维特丝 护发精油防毛躁清香玫瑰奇焕亮发干枯烫发卷发直发头发润发护发素男女士 滋养柔顺护发精油100ml
¥36.00