算法实操：Python代码实现直插排序(含有序在前有序在后)

直接插入排序法。有序部分在前、有序部分在后，均有Python代码实炼。

(本文获得CSDN质量评分【90】)

---

【学习的细节是欢悦的历程】

---

• Python 官网：https://www.python.org/

• Free：大咖免费“圣经”教程《 python 完全自学教程》，不仅仅是基础那么简单……

---

  自学并不是什么神秘的东西，一个人一辈子自学的时间总是比在学校学习的时间长，没有老师的时候总是比有老师的时候多。
            —— 华罗庚

---

• My CSDN主页、My HOT博、My Python 学习个人备忘录
• 好文力荐、 老齐教室

---

---

算法实操： Python代码实现直插排序 (含有序在前有序在后)

---

---

本文质量分：

【 90 】 本文地址： https://blog.csdn.net/m0_57158496/article/details/128140808

CSDN质量分查询入口：http://www.csdn.net/qc

---

---

◆ 直接插入排序法

◆ 算法原理：

  直接插入排序法，是在原数列操作，最好状态是一次遍历(本来有序的情况)；最差是全部乱序，依次遍历n-1次有序部分数列。
  把无序数列分成有序和无序两部分，每次取相相邻有序的一个数字和有序部分依次比对，直接插入相应位置。循环操作，直到整个数列变成有序，完成直接插入排序。

---

回页目录

---

1、有序部分在前

1.1 排序步骤(有序部分在前)

如对数列 8 6 9 4 3 2 排序

nums = [8, 6, 9, 4, 3, 2]
1

• 1、把第二个数字6取出，前为有序(一个数字天生有序)，后为无序。

[8] 6 [9, 4, 3, 2]
1

• 2、取出数字6与有序从后往前比对，比8小，插入8前。

[6, 8] [9, 4, 3, 2]
1

• 3、再次从无序部分取出紧邻有序的9，依次与8、6比对。9大于8，插入8后。

[6, 8] 9 [4, 3, 2]
[6, 8, 9] [4, 3, 2]
1
2

  重复执行第3步，直到整个数列变成有序，完成直接插入排序。

[6, 8, 9] [4, 3, 2]
[6, 8, 9] 4 [3, 2]
[4, 6, 8, 9] [3, 2]
[4, 6, 8, 9] 3 [2]
[3, 4, 6, 8, 9] [2]
[3, 4, 6, 8, 9] 2 []
[2, 3, 4, 6, 8, 9]
1
2
3
4
5
6
7

nums = [2, 3, 4, 6, 8, 9]
1

  完成直接插入排序

---

  算法逻辑明了了，代码实现就容易了。代码实现的关键点在于下标的引用和if判断条件语句的表达式的设定。由前面的分析过程可以看出，对有序部分的每次轮询是从下标i-1开始，到0结束(有序部分在前，取出了一个比对数字，有序部分的下标不受影响。无序部分元素下标位置前移一位，但代码实现排序过程中不用后面部分下标。每次只需取出i+1位置的数字，比对后直接插入合适的位置就好。)有序部分的下标，是从i-
1一直递减到0，记住这一点，一般就会顺利用代码实现直接插入排序(有序部分在前)了。代码优化：)1、如果比对数字比i-1大，就是已经有序，不用比对，直接用关键字continue跳转下一次轮询。2、成功插入比对数字后，后面的轮询就没有意义了，也用break跳出比对循环。

---

回页目录

---

1.2 直插排序代码(有序部分在前)

#!/usr/bin/nve python
# coding: utf-8
 

nums = list(map(int, input('\n输入数组(如[8 3 2)：').split()))
print('\n输入数组：', nums)

print(f"\n插入排序过程：\n{'':~^50}")

for i in range(1, len(nums)):

    j = i - 1

    if nums[i] > nums[j]: # 算法优化：为有序，不用执行后面的比对插入代码。直接跳过，执行下一循环。
        continue

    print(f"\n索引：{i}，比对插入排序数字：{nums[i]}\n列表状态：有序{nums[:i]}，无序{nums[i+1:]}") 

    temp = nums.pop(i) # 用pop()方法取出比对排序的数字。

    while j >= 0:
        if temp > nums[j]: # 在比比对数小的数后插入。
            nums.insert(j+1, temp)
            break # 插入后退出循环。
        j -= 1

    if j < 0: # 比所有有序数小，插入数列最前端。
        nums.insert(0, temp)

print(f"\n{'':~^50}\n插入排序后数组：{nums}\n")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

回页目录

---

1.3 运行效果截图

---

回页目录

---

2、有序部分在后

2.1 排序步骤(以有序在后)：

如对数列 8 0 9 4 2 1 0 6 排序

nums = [8, 0, 9, 4, 2, 1, 0, 6]
1

• 1、把第二个数字6取出，前为有序(一个数字天生有序)，后为无序。

[8, 0, 9, 4, 2, 1] 0 [6]
1

• 2、取出数字0与有序从前往前比对，比6小，插入6前。

[8, 0, 9, 4, 2, 1] [0，6]
1

• 3、再次从无序部分取出紧邻有序的1，依次与0、6比对。1小于6，插入6前。

[8, 0, 9, 4, 2] 1 [0，6]
[8, 0, 9, 4, 2] [0, 1, 6]
1
2

  重复执行第3步，直到整个数列变成有序，完成直接插入排序。

[8, 0, 9, 4] 2 [0, 1, 6]
[8, 0, 9, 4] [0, 1, 2, 6]
[8, 0, 9] 4 [0, 1, 2, 6]
[8, 0, 9] [0, 1, 2, 4, 6]
[8, 0] 9 [0, 1, 2, 4, 6]
[8, 0] [0, 1, 2, 4, 6, 9]
[8] 0 [0, 1, 2, 4, 6, 9]
[8] [0, 0, 1, 2, 4, 6, 9]
[] 8 [0, 0, 1, 2, 4, 6, 9]
[0, 0, 1, 2, 4, 6, 8, 9]
1
2
3
4
5
6
7
8
9
10

nums = [0, 0, 1, 2, 4, 6, 8, 9]
1

  完成直接插入排序

---

  算法理顺了，接下来就是代码实现。代码实现的关键点在于下标的引用和if判断条件语句的逻辑设定，下“有序在前”不同，比较是从前往后，下标是递增的。还有就是，比对的数字比前一个数字小，也不可以用前面用过的“代码优化”操作。由分析过程可以看出，对有序部分的每次轮询是从下标i+1开始，到n-2结束(有序部分在后，由于前面取出了一个比对数字，有序部分的下标就会减1，元素位置前移一位)记住这一点，一般就会顺利用代码实现直接插入排序(有序部分在后)了。

---

回页目录

---

2.2 直插排序代码(有序在后)

class MySortR:
    ''' 直插排序(后置有序) '''
    
    def __init__(self, nums):
        ''' 自动接收待排序数组并调用sort方法工作 '''
        self.sort(nums) # 自动调用sort进行直插排序工作。
    
    def sort(self, nums):
        ''' 直插排序操作 '''
        print(f"\n插入排序过程：\n{'':~^50}")

        n = len(nums)
        for i in range(n-2, -1, -1):
            print(f"\n索引：{i}，数字：{nums[i]}\n列表状态：无序{nums[:i]}，有序{nums[i+1:]}") 
            work = nums.pop(i) # 用pop方法取出比对数。
            k = i

            print('比对过程：')
            while k < n-1:
                print(f"{work:>11} → {nums[k]}")
                if work < nums[k]:
                    nums.insert(k, work) # 找到比取出比对数小的数，将比对数直接插入其后。
                    break

                k += 1

            if k > n - 2:
                nums.insert(n, work) # 在有序部分没有比取出比对数更大的数，直接将比对数插入有序之尾。
        # return 本方法是对列表原址操作，什么也不用返回。本方法不需return语句。
        
if __name__ == '__main__':
    nums = list(map(int, input('\n输入数组(如[8 3 2)：').split()))
    MySortR(nums)
    print(f"\n{'':~^50}\n插入排序后数组：{nums}\n")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

回页目录

---

2.3 直插排序比对工作过程

---

  CSDN博主“隰有游龙”的“老”文章——2021-04-14发布的博文“排序算法——直接插入排序”，对“直插排序法”有详细的图文讲解。有兴趣，可以点击蓝色文字跳转查看。

---

回页首

---

__上一篇：__ 炫技：拼接列表、破碎二维数组——Python sum()函数隐藏技能花式玩法

__下一篇：__ 

---

我的HOT博：

• Hot：个人信息提取(1402阅读)

• Hot：生成100个随机正整数(1453阅读)
• 给定字符串提取姓名(字符串、list、re“零宽断言”)(1051阅读)
• 我的 Python.color() (Python 色彩打印控制)(1463阅读)
• python清屏(2206阅读)
• 回车符、换行符和回车换行符(2165阅读)
• Linux 脚本文件第一行的特殊注释符(井号和感叹号组合)的含义(1379阅读)
• pandas 数据类型之 Series(1403阅读)
• 聊天消息敏感词屏蔽系统(字符串替换 str.replace(str1, *) )(1500阅读)
• 练习：银行复利计算(用 for 循环解一道初中小题)(1408阅读)
• pandas 数据类型之 DataFrame(3007阅读)
• ：班里有人和我同生日难吗？(蒙特卡洛随机模拟法)(2254阅读)
• Python字符串居中显示(3407阅读)
• 练习：求偶数和、阈值分割和求差( list 对象的两个基础小题)(1701阅读)
• 用 pandas 解一道小题(2056阅读)
• 可迭代对象和四个函数(1083阅读)
• “快乐数”判断(1286阅读)
• 罗马数字转换器(构造元素取模)(2324阅读)
• Hot：罗马数字(转换器|罗生成器)(5140阅读)
• Hot：让QQ群昵称色变的代码(42882阅读)
• Hot：斐波那契数列(递归| for )(4100阅读)
• 柱状图中最大矩形(1688阅读)
• 排序数组元素的重复起止(1286阅读)
• 电话拨号键盘字母组合(1460阅读)
• 密码强度检测器(2175阅读)
• 求列表平衡点(1875阅读)
• Hot： 字符串统计(4347阅读)
• Hot：尼姆游戏(聪明版首发)(3532阅读)尼姆游戏(优化版)(1242阅读)

• 
  

  推荐条件 点阅破千

  ---

  回页首

  ---

  
  

  精品文章：

  • 好文力荐：齐伟书稿 《python 完全自学教程》 Free连载(已完稿并集结成书，还有PDF版本百度网盘永久分享，点击跳转免费🆓下载。)
  • OPP三大特性：封装中的property
  • 通过内置对象理解python'
  • 正则表达式
  • python中“*”的作用
  • Python 完全自学手册
  • 海象运算符
  • Python中的 `!=`与`is not`不同
  • 学习编程的正确方法

  来源：老齐教室

  ---

  回页首

  ---

  ◆ Python 入门指南【Python 3.6.3】

  ---

  好文力荐：

  • 全栈领域优质创作者——寒佬(还是国内某高校学生)博文“非技术文—关于英语和如何正确的提问”，“英语”和“会提问”是学习的两大利器。

  • 【8大编程语言的适用领域】先别着急选语言学编程，先看它们能干嘛

  • 靠谱程序员的好习惯

  ---

  CSDN实用技巧博文：

  • 8个好用到爆的Python实用技巧
  • python忽略警告
  • Python代码编写规范
  • Python的docstring规范（说明文档的规范写法）

  ---