33 - 最日常的排序：插入排序

鱼C-小师妹

相信每位读者都玩过扑克牌吧～

在发好牌后，通常我们会进行整理，拿出一张牌，逐个比较。

大的就插在左边，小的就插在右边。当然这个顺序因人而异。

这么操作一轮后，手里的牌就整理好顺序了。

这和我们今天要讲的拆入排序非常类似～

插入排序法是：

将数列中的元素逐一与已排序好的数据进行比较，进而找到合适的位置并插入。

例如，在排好顺序的两个元素中插入一个元素，就需要将其与其他两个元素做比较，插入合适的位置。

也就是说，将新元素插入数列后，得到的新数列依然是排好序的。

接着再插入另一个元素，以此类推，直至排序完成。

插入排序法最后的结果无非就是两种形式：

递增数列或者递减数列。

假设有一组无序数据：99，23，15，44，3

按照从小到的顺叙进行排序。

第一次排序

先将首位数字 99 放入已排序区域：99

第二次排序

将第二个元素 23 与已排序区域的元素进行比较。

23 小于 99，插入到 99 之前。

此时已排序区域：23，99

第三次排序

将第三个元素 15 与已排序区域元素依次比较。

15 小于 25，15 插入到 25 之前。

此时已排序区域：15，23，99。

第四次排序

将第四个元素 44 与已排序区域元素依次比较。

44 大于 15，23，但小于 99，所以插入到 23 后面，99 后移一个位置。

此时已排序区域：15，23，44，99。

第五次排序

将第五个元素 3 与已排序区域依次比较。

3 小于 15，插入到前面。

此时已排序区域：3，15，23，44，99。

至此排序结束。

接下来我们通过代码实现上述过程。

初始化部分和之前一样：

1. data = [99,23,15,44,3]
   
2. print("原列表：",data)   
   
3. print('\n----我是分界线------\n')
   
4. insert(data)

复制代码

我们来实现 choose(data)：

1. def choose(data):

复制代码

还是要先遍历数据，创建一个变量 t 表示暂存数据：

1.     for i in range(len(data)):
   
2.         t = data[i]

复制代码

从上面的排序我们知道每次都会从原数列中取出一位。

那么我们的对比值 j 的下标就要 i-1:

1.         j = i - 1

复制代码

接下来通过循环排序，判断数据的下标值要大于等于 0 且暂存数据小于原数据。

然后就把所有元素往后移一位并且下标减 1：

1. while j >= 0 and t < data[j]:
   
2.             data[j+1] = data[j]
   
3.             j -= 1

复制代码

完成循环后，将最小的数据插入最前一个位置：

1. data[j + 1] = t

复制代码

剩下就是打印结果：

1.         for j in range(len(data)):
   
2.             print(data[j],end=' ')
   
3.         print()

复制代码

执行看下结果：



源码： insert.py.zip (863 Bytes, 下载次数: 5, 售价: 6 鱼币)

2022-3-28 17:48 上传

点击文件名下载附件

接下来我们基于插入排序将 5 位同学的 C 语言考试成绩用插入排序实现从小到大排序，并输出冠亚季军：



数据：

1. data = {'小甲鱼':99,'小田鱼':90,'小电鱼':84,'小由鱼':76,'小申鱼':88}   

复制代码

因为 data 是字典，我们用 31 讲说过的 list() 将其改为列表，并循环输出：

1. print("5名同学初始成绩：")
   
2. data = {'小甲鱼':99,'小田鱼':90,'小电鱼':84,'小由鱼':76,'小申鱼':88}  
   
3. data2 = list(data.items())
   
4. print(data2)
   
5. for i in data2:
   
6.     print(i)

复制代码

程序初始化部分完成了，剩下就是先调用我们的 insert 函数进行排序啦：

1. def insert(data):

复制代码

因为都是插入排序，核心部分代码结构肯定一样：

1. def insert(data):
   
2.     for i in range(len(data)):
   
3.         t = data[i]
   
4.         j = i - 1
   
5.         while j >= 0 and key(t) < key(data[j]):
   
6.             data[j+1] = data[j]
   
7.             j -= 1
   
8.         data[j + 1] = t

复制代码

由于我们的数据包含人名和成绩，我们需要按照人名排序，即返回每个位置 1 处值即可：

1. def key(x):
   
2.     return x[1]

复制代码

执行完代码后，data2 中数据就会按照从小到大进行进行排序：

1. insert(data2)

复制代码

直接输出后三位值即可：

1. print('\n----最终排名------\n')
   
2. print('冠军是：',data2[4])
   
3. print('亚军是：',data2[3])
   
4. print('季军是：',data2[2])

复制代码

因为此时数据长度为 5，我们可以直接通过下标来输出。

如果数据长度不定，那么后三位就是 [len(data)-1]，[len(data)-2]，[len(data)-3]。

好啦，代码留给你们自己去实现。

源码： insert.py.zip (941 Bytes, 下载次数: 4, 售价: 10 鱼币)

2022-3-29 17:07 上传

点击文件名下载附件

下课！

阿萨德按时

threeing3

sls111

学习学习

hornwong

a2437883405

0.0

Xie2002

看看

憨憨学py

def choose(data):
    for i in range(len(data)):
        t = data[i]
        j = i - 1
        while j >= 0 and data[j] > t:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = t
        print(f"第{i+1}次排序后:",end=' ')
        for j in range(len(data)):
            print(data[j], end=' ')
        print()


data = [99, 23, 15, 44, 3]
print("原列表：", data)
print('\n----我是分界线------\n')
choose(data)