1.5 插入排序

[utterances-bot]

1.5 插入排序

插入排序 # 1. 插入排序算法思想 # 插入排序（Insertion Sort）基本思想： 将整个序列分为两部分：前面 i 个元素为有序序列，后面 n - i 个元素

https://algo.itcharge.cn/01_array/01_05_array_insertion_sort/

[guzhe1107]

简单来说，「选择排序算法」是在每一趟排序中，将无序序列的第 1 个元素，插入到有序序列的适当位置上。
这里应该是「插入排序算法」

[itcharge]

简单来说，「选择排序算法」是在每一趟排序中，将无序序列的第 1 个元素，插入到有序序列的适当位置上。 这里应该是「插入排序算法」

已修正，感谢指正~~

[hanxiang0227]

打卡

[surpoloyang]

for i in range(1, len(nums)):
insert_i = i
for j in range(i-1, -1, -1):
if nums[j] > nums[i]:
insert_i = j
if insert_i != i:
nums.insert(insert_i, nums.pop(i))
这是我写的代码，请指正~

[surpoloyang]

2.2步应该是比num[1]大的元素向后移动一位吧

[cattytyty]

离谱就

[Wan-Yifei]

确实，感觉全写反了。

[wudiheike]

这个部分确实写错了，看菜鸟教程的动图一下子明白了

[T1anq1]

文字描述部分是否写反了？“从右到左遍历有序区间中的元素，将比 𝑛𝑢𝑚𝑠[1]小的元素向后移动 1 位。”，是否应该是将比num[1]大的元素往后移动一位？按照原文的说法输出就会是从大到小而不是从小到大。

[Jiurouqiu8]

自己改下缩进
def insertion(lst):
for i in range(1,len(lst)):
temp = lst[i]
j = i - 1
while j >= 0 and lst[j] > temp:

            lst[j+1] = lst[j]
            j -= 1

    else:
            lst[j+1] = temp
return lst

lst = [5,2,3,6,1,4]
print(insertion(lst))

[Jiurouqiu8]

#选排找最小
    def find_min(lst):
    min_ind = 0
    for i in range(1,len(lst)):
        if lst[i] < lst[min_ind]:
            min_ind = i
    return min_ind

#选择排序-先找剩余最小再与剩余第一位交换
    def select_sort(lst):
    for i in range(len(lst)):
        temp = lst[i]
        for j in range(i+1,len(lst)):
            ind = find_min(lst[i:]) + i
            if lst[ind] < lst[i]:
                lst[i] = lst[ind]
                lst[ind] = temp
    return lst
lst = [5,2,3,6,1,4]
print(select_sort(lst))

[Jiurouqiu8]

这样想完全就是按照过程和图解来的哈哈哈，先找最小值的索引（不使用min）然后就选择排序
但是po主的码最方便也是最常见的，比较的是值，没必要存储一遍最小值的索引

[medrawtan]

    for i in range(1,len(nums)):
        j=i
        while j>0 and nums[j-1]>nums[j]:
            nums[j-1],nums[j]=nums[j],nums[j-1]
            j-=1
    return nums

自己写了一个简单的

[kuangxiaozi12138]

for (int i = 1; i < arr.size(); i++) {
	for (int j = i-1; j >= 0; j--) {
		if (arr[i] < arr[j]) {
			swap(arr[i], arr[j]);
		}
	}
}

这样子写应该不算是插入排序吧

[kuangxiaozi12138]

感觉插入排序的精髓是找到最小的索引然后直接插入进去

[Wan-Yifei]

个人感觉有序区间内的比较和插入其实就是冒泡算法，不过改成了从右向左，遇到大于temp的值就交换位置，知道遇到比temp小的，此时temp已经被连续交换送到了恰当的位置。