chapter_sorting/insertion_sort/

[giscus[bot]]

chapter_sorting/insertion_sort/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_sorting/insertion_sort/

[L-Super]

发现一个小问题，vector<int>& nums由于字体的缘故，&引用符与常规不太一致。我注意到的时候，以为是不是符号错了。个人小建议：可以换个不误导的字体，毕竟如果是定位小白入门的话，符号最好与主流显示一致。仅供参考，无伤大雅

[krahets]

谢谢建议！感觉总体来说这个字体还是优点更多，比如可以正确区分 1 和 l、O 0 等。

[FangYuan33]

K神，插入排序的核心思想这么写会不会更容易理解和记忆呢：取未排序区间中的某个元素为基准数 base，将 base 与其左侧已排序区间元素依次对比大小，并"插入"到正确位置，参考 数据结构与算法之美 P61

[krahets]

确实分为“排序”和“未排序”区间会更清晰～

[Rabbit937]

和斗地主，理扑克一个逻辑哦

[krahets]

确实，整理牌的方法和插入排序思想一样

[WhiteRhinos]

/**
 * 希尔排序
 * 是对插入排序的改进,插入排序,如果是5,3,,4,8,1这种最小数在很后面就会进行多次交换
 * 希尔排序采用分组加插入排序处理这个问题,将长度/2为分组数量,每个分组在进行插入排序,
 * 当步长为1的时候就是简单插入排序,不过此刻数据基本有序,只需要进行少量的交换
 * @param ints 数组
 * @param gap 组数
 */
public static void shellSort(int[] ints, int gap)
{
    // 组数<1结束
    if (gap < 1)
    {
        return;
    }
    // 有序判断,如果有序就直接结束
    // if (isSorted(ints, 0, ints.length))
    // {
    //     return;
    // }

    // 组数
    gap /= 2;
    // 步长
    int step = gap;

    // 对每一组进行排序,i表示每组首元素的下标
    for (int i = 0; i < gap; i++)
    {
        // 对同一组的进行插入排序(和插入排序一样不过插入排序步长为1,这里步长会变)
        // j表示同组的下标
        for (int j = i + step; j < ints.length; j += step)
        {
            // 暂存有序区首位元素
            int temp = ints[j];
            int k = 0;
            for (k = j - step; k >= 0; k -= step)
            {
                if (temp > ints[k])
                {
                    break;
                }
                // 后移
                ints[k + step] = ints[k];
            }
            // 插入
            ints[k + step] = temp;
        }
    }
    // System.out.println("分为" + gap + "组");
    // System.out.println(Arrays.toString(ints));
    // 递归
    shellSort(ints, gap);
}

[zhuasdfg]

太强了，看了好久才看明白，这种算法不稳定吧，这个是分治吗，分成gap份处理

[WhiteRhinos]

是对插入排序的改良,只是加入的步长,还是稳定的,有分治法的思想在

[WhiteRhinos]

代码上就是在插入排序外层在嵌套了一层for循环进行分组的遍历,分组是按照步长来划分

[frcoo]

确实牛，但有点小瑕疵，计算gap那一步，应该放在递归处吧：
// 递归
shellSort(ints, Math.floor(gap / 2));

[FantasyLeo]

为什么我觉得插入排序和冒泡排序基本一样？冒泡排序需要一个tmp临时变量用于交换，插入排序也需要一个base变量。区别在于插入不是每一次都在交换，而是直到找到合适位置，但是我感觉这根本上没多大区别。另外元素“参与”排序的顺序不一样，一个头开始，一个从低开始。本质还是没区别么。。求人解答一下。

[krahets]

选择、冒泡、插入的基本思想都是：每一轮完成一个元素的排序，并将这个过程循环 n-1 轮。

三者在“每一轮完成一个元素的排序”的做法是不一样的。冒泡排序是基于相邻元素交换、插入排序是基于数组插入操作。

[2511342225]

我也总觉得插入排序和冒泡排序很像，想了好一会儿想到冒泡排序是先排好最大的，再第二大，这样由大到小冒泡。但是插入排序每一次就是按照数组的顺序把这个元素插到合适的位置。

[DXShelley]

三点改进：
一简化循环结构，条件放到内部，更易读；
二如果基准元素找到安置位置即跳出循环；
三如果基准元素就是安置位置，无需赋值操作；
public  void insertionSort3(int [] array) {
        // 外层循环 基准元素依次从左到右
        for (int i = 0; i < array.length; i++) {
            int base = array[i];
            // 内层循环 依次从右到左，遍历已排序区间，查找基准元素合适安置位置 
            int j = i;
            while (j > 0) {
                if (array[j - 1] > base) {
                    // 前边元素依次赋值后续元素，实现移动效果
                    array[j]= array[j - 1];
                } else {
                    // 如果基准元素已到达指定位置，无序继续比较下去。因为已排序区间为有序，第一个小于基准元素的话，该元素前边都小于基准元素。
                    break;
                }
                j --;
            }
            // 若已排序区间发生元素移动，才会赋值操作。
            if (j != i) {
                 // j的区间为[0，i]，不用考虑越界问题。由于break，此处j值对应上轮的array[j-1] 或array[0]。
                array[j] = base;
            }
        }
    }

[krahets]

谢谢分享！因为你提到了“改进”，则需要澄清：

二如果基准元素找到安置位置即跳出循环；

文中代码同样包含这个特性。

三如果基准元素就是安置位置，无需赋值操作；

只有在 j == i 时，可以省去一次赋值操作，但每一轮都增加了一次 if (j != i) 判断操作，因此效率不一定更高。

[DXShelley]

• 插入排序，也可以理解为尝试用基准元素和有序区间元素，从后往前依次对比，大于基准元素就交换- 位置，最终基准元素会到达合理安置位置，无序最后赋值操作。
• 与冒泡排序有些许区别：一个无序元素冒泡排序一个循环后，是最终位置；而插入排序，只是有序区间局部有序，无法确定是最终位置。
• 选择排序每次都先选择无序区间内最大（或最小值）与尾部（或头部）交换，形成有序区间；而插入排序每次都是在有序区间内查找安置位置。

[5710xIa]

😁说到扑克，我都喜欢拿到全部牌后再一张张摸，这样比直接全抓起来理的舒服点。

那么插入排序能不能直接另创一个数组，直接挨个元素往新数组加，加入新数组用二分查找，遇上值相同的直接插入，都不用考虑左右了。

[krahets]

人整理扑克的方式和你说的是类似的，用二分（跳跃式）搜索来找插入位置。

但在计算机中，就算我们用二分找到了插入点，插入元素还是需要将该位置右边的元素全部向右移动一位（即数组插入操作）。因此性能瓶颈在元素移动，而不是搜索。这也是插入排序中不包含二分搜索的原因。

[NIDIEJIE]

k神，感觉可以把希尔排序加上

[krahets]

好的收到～

[lianyeyuxia]

这里 java while语句里面，如果j=0，还会执行 j--么

[krahets]

会呀，循环条件是 while (j >= 0 && nums[j] > base) ，j = 0 时是会进入执行循环体的。

[hello-ikun]

可以填一下 折半插入排序 希尔排序

[lets2zg]

/// Stable in-place sort. O(n) best case, O(pow(n, 2)) worst case.
/// O(1) memory (no allocator required).
/// Sorts in ascending order with respect to the given `lessThan` function.
pub fn insertion(
    comptime T: type,
    items: []T,
    context: anytype,
    comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
    const Context = struct {
        items: []T,
        sub_ctx: @TypeOf(context),

        pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
            return lessThanFn(ctx.sub_ctx, ctx.items[a], ctx.items[b]);
        }

        pub fn swap(ctx: @This(), a: usize, b: usize) void {
            return mem.swap(T, &ctx.items[a], &ctx.items[b]);
        }
    };
    insertionContext(0, items.len, Context{ .items = items, .sub_ctx = context });
}

zig标准库的插入排序赋值有点多了,不知在zig标准库中可否改进?

[Hyrmm]

function insertionSort(nums) {
    for (let i = 1; i < nums.length; i++) {
        let base = nums[i]
        let j = i - 1
        while (i >= 0 && nums[j] > base) {
            // 交互位置
            nums[j + 1] = nums[j]
            nums[j] = base
            j--
        }

    }
    return nums
}

这样写应该还算插排，唯一差别就是将base和已排好的排比较，大的就交换位置

[weiwenlong555]

这样连续交换位置感觉像冒泡

[2511342225]

感觉这样写多了一次赋值操作

[KLYkl]

这个写法，首先while (i >= 0 && nums[j] > base)里的nums[j]会越位，比如说i=1，在数组{1，2}中，循环满足（i >= 0 && nums[j] > base），里面执行了j--，当第二次判断是，i>=0满足，进行nums[j]>base判断时，nums[j]明显越界了。
如果你想写的是while (j >= 0 && nums[j] > base)，那没必要多执行可能将近j次的nums[j] = base。

[RENHJa]

请问大神，nums[j + 1] = base; 这一步不是很理解，他的作用是什么？可以删掉吗？

[krahets]

当然不行啦，nums[j + 1] = base; 这是把待插入元素 base 赋值到正确位置，前面的 for 循环向右移动元素就是为了这一步铺垫的

[RENHJa]

我懂了大神，谢谢，我理解了！！！后面我独自写了一遍，稍微有点修改

[Bellxu]

有点像打牌的时候抽一张放到手里牌正确位置的感觉

[summer-breeze123]

这个比喻绝了

[shijieyangsir]

public static void main(String[] args) {

        List<Integer> list = new ArrayList<Integer>();
        List<Integer> temp = addItem(list);
        for (int i = 1; i < temp.size(); i++) {
            for (int j = 0 ; j < i; j++) {
                if (temp.get(i) < temp.get(j)) {
                    Integer tempItem = temp.get(j);
                    temp.set(j, temp.get(i));
                    temp.set(i, tempItem);
                }
            }   
        }
        System.out.println(temp);
    }

    public static List<Integer> addItem(List<Integer> list) {
        list.add(1);
        list.add(0);
        list.add(16);
        list.add(16);
        list.add(1);
        list.add(3);
        list.add(7);
        list.add(9);
        list.add(11);
        list.add(5);
        return list;
    }

请教下 java这样写 算是插入排序嘛

[krahets]

没太看懂，不过由于包含了元素交换操作，因此应该不是插入排序

[2511342225]

新人刚学算法，下意识用了两个for 循环而不是while，但是这样会多一次赋值操作，不知道怎么优化呢？

def insertion(nums):
    n=len(nums)
    for i in range(1,n):
        base=nums[i]       
        for j in range(i-1,-1,-1):
            if nums[j]>base:
                nums[j+1]=nums[j]
                nums[j]=base #多了一次赋值操作
            else:
                nums[j+1]=base
                break

[480284856]

def insertion_sort1(nums: list[int]):
    # 遍历数组
    for for_inserted in range(1, len(nums)):
        element_for_inserted = nums[for_inserted]
        # 排好序的有序子数组的右边界
        for finished in range(for_inserted-1, -1, -1):
            if(nums[finished] > element_for_inserted):
                nums[finished+1]=nums[finished]
            else:
                nums[finished+1]=element_for_inserted
                break
        else: # element_for_inserted应该放到第一个，但python的for循环自然跳出时，finished为0
            nums[finished]=element_for_inserted

[summer-breeze123]

感觉可以添加一下折半插入排序

[summer-breeze123]

简单写了一下插入+折半排序，应该没什么问题

/*折半插入排序*/
/*折半插入排序*/
void insertionBinarySort(std::vector<int> &nums) {
    int n = nums.size();
    // 外循环，已排序区间为 [0, i-1]
    for (int i = 1; i < n; i++) {
        int base = nums[i];
        int low = 0;
        int high = i - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] > base) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        // 将区间 [low, i-1] 的元素右移，腾出位置给 base
        for (int j = i; j >= low + 1; j--) {
            nums[j] = nums[j - 1];
        }
        // 将 base 插入到正确位置
        nums[low] = base;
    }
}

[Gpihuier]

推荐一个数据结构和算法可视化的网站：VisuAlgo

[yangxz217]

看k神的源码之前自己写的，多用了一次循环

def insertion_sort(nums: list[int]):
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] > nums[i]:
                tmp = nums[i]
                for k in range(i, j - 1, -1):
                    nums[k] = nums[k - 1]
                nums[j] = tmp