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]

这个比喻绝了

[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

[wqk756633]

python中没有中间变量，C中有中间变量

[Introsb]

是swap函数内部借用了一个临时变量吗

[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;
}

[sabully]

def insert_sort(arr):
    '''插入排序'''
    for i in range(1, len(arr)):
        value = arr[i]
        while i > 0 and value < arr[i - 1]:
            arr[i - 1], arr[i] = arr[i], arr[i - 1]
            i -= 1
    return arr
感觉这样写代码更容易理解

[LunFengChen]

理解，不过效率变低了

[zhuiguang49]

对于插入排序算法特性的部分有一点小疑问，每次插入操作应当分别需要循环1,2,...,n-1次？看描述是n-1,n-2,...,2,1次，似乎反过来了

[wantongren]

func InsertSort(nums []int) []int {
n := len(nums)
for i := 1; i < n; i++ {
for j := i; j > 0; j-- {
if nums[j] < nums[j-1] {
nums[j], nums[j-1] = nums[j-1], nums[j]
}
}
}
return nums
}
这样写感觉更容易理解

[batreeon]

func insertionSort(nums []int) {
	// 外循环：已排序区间为 [0, i-1]
	for i := 1; i < len(nums); i++ {
		// base := nums[i]
		// j := i - 1
		// // 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
		// for j >= 0 && nums[j] > base {
		// 	nums[j+1] = nums[j] // 将 nums[j] 向右移动一位
		// 	j--
		// }
		// nums[j+1] = base // 将 base 赋值到正确位置
		
		for j := i - 1; j >= 0; j-- {
			if nums[j+1] < nums[j] {
				nums[j+1], nums[j] = nums[j], nums[j+1]
			} else {
				break
			}  
		}
	}
}

[xiaoyaozizaiwoweidu]

希尔排序算法

def shell_sort(arr):
    """
    使用自定义的插入排序逻辑，逐步缩小增量 gap，完成整个数组的排序。
    """
    # 获取列表的长度
    n = len(arr)
    # 初始化增量 gap，初始值为数组长度的一半
    gap = n // 2

    # 循环到 gap 不能分割为止
    while gap > 0:
        # 对每个子序列进行插入排序
        for i in range(gap, n):
            # 记录下来要比较的数据
            tmp = arr[i]
            # 记录位置
            j = i
            # 判断是否要做插入排序，j >= gap 判断是否还有数据要比较，
            # arr[j - gap] > tmp 判断是否满足插入排序条件
            while j >= gap and arr[j - gap] > tmp:
                arr[j] = arr[j - gap]  # 将 arr[j - gap] 向右移动一位
                j -= gap
            arr[j] = tmp  # 将 tmp 赋值到正确位置

        # 缩小增量 gap
        gap = gap // 2

[xiaoyaozizaiwoweidu]

《算法 4》中给的递增函数是(3、- 1)/2，即 1,4,13,40,121,364...

def shell_sort(nums):
    """
    希尔排序算法
    使用增量序列 (3^k - 1) / 2，即 h = 1, 4, 13, 40, 121, 364...
    对每个子序列进行插入排序，逐步缩小 h，最终完成整个数组的排序。
    """
    n = len(nums)  # 获取数组长度

    # 初始化增量 h，使用生成函数 (3^k - 1) / 2
    h = 1
    while h < n // 3:  # 确保 h 的初始值足够大
        h = 3 * h + 1  # 按照生成函数计算 h

    # 主循环：逐渐缩小 h，直到 h = 1
    while h >= 1:
        # 对每个子序列进行插入排序
        for sorted_index in range(h, n):
            # 记录当前要插入的元素
            tmp = nums[sorted_index]
            # 从当前元素开始，向左遍历子序列
            i = sorted_index
            while i >= h and nums[i - h] > tmp:
                # 将较大的元素向右移动
                nums[i] = nums[i - h]
                i -= h
            # 将当前元素插入到正确位置
            nums[i] = tmp

        # 按照递增函数的规则，缩小 h
        h //= 3  

[liguohan]

这篇文章画演示更好理解：https://mp.weixin.qq.com/s/iJvPegXpBRI6dkzLWEE6dA

[liguohan]

这篇文章动画演示更好理解：https://mp.weixin.qq.com/s/gpJgLEk1Ayxjw65_V-6jGg

[xiaozhuge123]

day09