插入排序

/**
 * 插入排序
 */
@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;
    }

}

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


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