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));

[3Ajfdjsdsk2]

我的理解是这样的：希尔排序的最后一层循环（也就是i=0，step=1）就是插入排序，只不过前面几次循环把小的数安置的位置更加前面了，所以在这最后一个循环里大部分走的都是【if (temp > ints[k]) break；】
从而加快了速度

[FantasyLeo]

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

[krahets]

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

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

[2511342225]

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

[syutengu]

冒泡的关键操作是邻座两两换位，
插入是比基准值大的人全部给它让座。
有点反直觉地，两两换位开销大于顺次让座。
能想到的比喻是，
两两让座需要双方都把屁股挪开座位，
而顺次让座只要一方直接坐到他人座位上去就行了（尽管这个座位上有人），
屁股离席的开销，冒泡更大。

[syutengu]

联想到一句俚语，请神容易送神难。覆盖容易交换难。

[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]

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

[Jetmores]

/// 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]

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

[summerBreeze03]

这个比喻绝了

[Yerosius]

没有希尔排序？

[shengpj]

“插入排序基于元素赋值实现，仅需 1 个单元操作”，对这句不是很理解，插入排序不是还要移动数组吗，while循环中将 nums[j] 向右移动一位？

[krahets]

这句话目的是将插入排序的“元素赋值”和冒泡排序的“元素交换”进行对比，两者分别包含 1 和 3 个单元操作

[redandblueqwer]

我的理解是为了对比两种算法元素调位置时的操作，也就是内层循环中每一次需要调位置时，插入排序执行是的赋值操作，冒泡排序需要的操作是交换。

[syutengu]

冒泡需要频繁地编织第三个临时篮子，用以交换两个篮子里的鸡蛋。
而每次交换都需要重复左蛋放临篮，右蛋放左篮，（临篮中的）左蛋放右篮，这三个操作。//*3

而插入是开始内循环前编织一个临时篮子，用来放基准值左邻篮子里的鸡蛋，//+1
然后频繁执行单纯的左蛋放入右篮的操作，//*1
内循环结束时把临时篮子里的鸡蛋放入[j+1]篮子。//+1

所以应该是冒泡开销更大，不知道这样理解对吗。

[syutengu]

用来放基准值左邻篮子里的鸡蛋❌
用来放基准值这个鸡蛋✔

[panumat]

一个小优化，使用一个变量保存base，然后逐个后移base前方的元素，其实等同于将base不断往前交换位置，说白了这就是一个反向的冒泡过程，我觉得把它称作沉底排序会更形象，然后这个base实际是已排序区间和未排序区间的分割点，这个过程就是一个未排序区间的首元素不断向已排序区间交换位置的过程，一旦遇上小于等于自身的元素，则代表当前已到达正确的位置，即可结束本轮内层循环
这个是我试着优化后的python代码

def insertion_sort(arr: list) -> None:
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] >= arr[j - 1]:
                break
            arr[j], arr[j - 1] = arr[j - 1], arr[j]

[MaikieMaiky]

你这个是冒泡排序吧,元素交换依旧需要使用三个单元操作
这并不是插入排序

[yanhua-volvo]

还是感觉看《算法》书中讲的更容易懂一些：从数组的第i元素开始遍历(第0个本身有序)，然后内层循环实现将a[i]插入到a[i-1],a[i-2]...a[0]中。

[ThxUuu]

是的，你的代码实现了插入排序。插入排序是一种简单的排序算法，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 你的代码逻辑如下： 1. 从第二个元素开始（i = 1），遍历列表。 2. 对于每个元素，向前扫描已排序部分（j = 0 到 i-1）。 3. 如果当前元素小于已排序部分的元素，则交换它们的位置。 这种逻辑正是插入排序的核心思想。每次内层循环完成时，temp列表的前i+1个元素都是有序的。 不过，插入排序通常是在插入过程中将元素移动到合适位置，而不是通过交换完成。因此，虽然你的实现达到了插入排序的效果，但严格来说更接近冒泡排序的交换方式。若要更符合插入排序的标准，可以考虑在插入时将较大的元素移动，而不是交换。 比如： 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++) { int key = temp.get(i); int j = i - 1; // 向后移动比key大的元素 while (j >= 0 && temp.get(j) > key) { temp.set(j + 1, temp.get(j)); j--; } // 插入key到正确位置 temp.set(j + 1, key); } 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; }

…

________________________________ 发件人: lianyeyuxia ***@***.***> 发送时间: 2023年11月10日 3:29 收件人: krahets/hello-algo ***@***.***> 抄送: Subscribed ***@***.***> 主题: Re: [krahets/hello-algo] chapter_sorting/insertion_sort/ (Discussion #59) 这里 java while语句里面，如果j=0，还会执行 j--么 ― Reply to this email directly, view it on GitHub<#59 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/APP7YV6YZKAKNN4BT67HBDTYDWNQXAVCNFSM6AAAAAASRAG2JGVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TKMRZGI3TE>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[yin-b]

好奇作者流程图怎么画的？

[CodeGetters]

我觉得插入排序思路可以写成 斗地主抓牌整理牌 这个例子更好理解

[sanzhang007]

虽然很像冒泡排序，但是一个天一个地，差别太大了。快几十倍都有可能

[sanzhang007]

小数据量最快的排序方式

[checkma-xh]

def sort(nums):
    for i in range(1, len(nums)):
        base = nums[i]

        while i > 0 and base <= nums[i - 1]:
            nums[i] = nums[i - 1]
            i -= 1

        nums[i] = base
    
    return nums


sort([1,3,32,4,1,-100,23,17,23,6,-7,2,9,-1000])

[Chr1sdian]

第二遍学习 自己写了个插排的算法 可以实现排序，但每进行一次循环就要赋一次值，相较于整体循环结束后再赋值显得低效 而且貌似还有优化的空间
def insertion_sort_i(nums):
n = len(nums)
for i in range(1,n):
base = nums[i]
for j in range(i,-1,-1):
if j>0 and nums[j-1] > base:
nums[j],nums[j-1] = nums[j-1],base

[Chr1sdian]

这格式怎么变成这样了...

[TianMaker]

“冒泡排序基于元素交换实现，需要借助一个临时变量”这里说的临时变量是哪个啊

[Clemna10]

temp

[1hew]

def insertion_sort_with_binary(nums: list[int]):
"""
使用二分查找优化插入排序
减少了比较次数
"""
def binary_search(nums, val, start, end):
"""在已排序区域中使用二分查找插入位置"""
while start < end:
mid = (start + end) // 2
if nums[mid] < val:
start = mid + 1
else:
end = mid
return start

n = len(nums)
for i in range(1, n):
    current = nums[i]
    # 使用二分查找找到插入位置
    pos = binary_search(nums, current, 0, i)
    # 从后往前移动元素
    for j in range(i, pos, -1):
        nums[j] = nums[j - 1]

    nums[pos] = current
return nums

nums = [1, 3, 32, 4, 1, -100, 23, 17, 23, 6, -7, 2, 9, -1000]
insertion_sort_with_binary(nums)

[1hew]

def shell_sort(nums: list[int]):
"""
基础希尔排序
通过逐步减少间隔（步长）来对数组进行排序
"""
n = len(nums)
# 计算步长
gap = n // 2 # 初始步长为数组长度的一半

# 遍历进行更新操作
while gap > 0:  # 当步长大于0时，继续排序
    # 对每个子序列进行插入排序
    for i in range(gap, n):  # 从步长位置开始遍历数组
        # 保存当前待插入的元素
        current = nums[i]
        j = i
        # 在子序列中进行插入排序
        while j >= gap and nums[j - gap] > current:  # 如果前面的元素大于当前元素
            nums[j] = nums[j - gap]  # 将前面的元素后移
            j -= gap  # 移动到前一个位置
        nums[j] = current  # 将当前元素插入到正确位置

    gap = gap// 2  # 减小步长，继续排序
return nums

nums = [1, 3, 32, 4, 1, -100, 23, 17, 23, 6, -7, 2, 9, -1000]
shell_sort(nums)

[Ayerchi]

个人理解插入和冒泡的区别在于中间变量的实际赋值发生位置是否在子循环内部，冒泡类似滑动窗口，而插入则是查询下标进行插入替换，所有具体优化思路也会不一样

   public static int[] insertSort(int[] nums) {

    for (int i = 1; i < nums.length; i++) {

        /* 写的第一版 temp在循环内创建 实际是冒泡 并非插入排序
        for (int j = i; j > 0; j--) {
            if (nums[j] < nums[j - 1]) {
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }
        }

        // for 形式
        int base = nums[i];
        int k = i;
        for (int j = i - 1; j >= 0; j--) {
            if (base < nums[j]) {
                nums[j + 1] = nums[j];
                k = j;
            } else {
                break;
            }
        }
        nums[k] = base;

        */

        // while 形式
        int base = nums[i];
        int j = i - 1;
        int k = i;
        while (j >= 0 && base < nums[j]) {
            nums[j + 1] = nums[j];
            k = j;
            j--;
        }

        nums[k] = base;

    }

    return nums;
}