直接插入排序

　　　　　　　　　　　　　　　　直接插入排序

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　作者：尹正杰

一.直接插入排序（Direct insertion sort）概述

在为排序序列中，构建一个子排序序列，直至全部数据排序完成

将代排序的数，插入到已经排序的序列中合适的位置

增加一个哨兵，放入比较值，让它和后面已经排好的序列比较，找到合适的插入点

二.直接插入排序原理

初始值：[1 9 8 5 6]

第一趟：[0 1 9 8 5 6] [9 1 9 8 5 6]  -> [1 9 8 5 6]    　　　　　　　　　　　　　　　　#如大家所看到的，和初始值必须，我在第一个位置上增加了一个数字0，这个数字0的位置我们称其为哨兵，接下来我们直接取初始值的第二个索引9和它前面一个索引比较（第一个索引相比较），哨兵9比1大，则不需要交换位置，本轮比较结束。

第二趟：[8 1 9 8 5 6] [8 1 ? 9 5 6] [8 1 8 9 5 6] -> [1 8 9 5 6]　　　　　　　　　　 #拿到上一轮比赛结果，接下来我们直接取初始值的第三个索引8和它前面一个索引比较，本轮哨兵为8，而哨兵8比9小，因此，我们需要把9往右移动一位，此时哨兵被插入8和9交换位置索引变为第二个索引，此时依旧需要和前面的一个索引进行比较，很显然第一个索引为1，而哨兵为8，哨兵8比1大，则不需要交换位置，本轮比赛结束。（简单的说就是如果比本轮哨兵大就相互交换位置，如果比本轮哨兵小则本轮结束）

第三趟：[5 1 8 9 5 6] [5 1 8 ? 9 6] [5 1 ? 8 9 6] [5 1 5 8 9 6] -> [1 5 8 9 6]　　 #拿到上一轮比赛结果，接下来我们直接去初始值的第四个索引5和它前面一个索引比较，本轮哨兵为5，而哨兵5比9小，因此他们需要相互交换位置，接着哨兵5再和它前面一个索引比较，哨兵5比8小，继续交换位置，然后继续和它前面一个索引比价，发现哨兵5比1大，终止本轮比赛。

第四趟：[6 1 5 8 9 6] [6 1 5 8 ? 9] [6 1 5 ? 8 9] [6 1 5 6 8 9] -> [1 5 6 8 9]    #拿到上一轮的结果，继续重复插入排序比较，经过上面3次比较，想必大家也清楚它是如何排序的了，最终经过四趟比较，得到的排序是：1 5  6 8 9

三.使用Python代码实现直接插入排序

 1 #！/usr/bin/env python
 2 #_*_coding:utf-8_*_
 3 #@author :yinzhengjie
 4 #blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
 5 #EMAIL:y1053419035@qq.com
 6 
 7 """
 8 思路：
 9     增加一个哨兵位，每轮比较将比较数放入
10     哨兵依次和前一个数据比较，大数靠右移动，找到哨兵中值的插入位置
11     每一轮结束后，得到一个从开始到待比较数位置的一个有序序列
12 
13 插入排序特点：
14     最好情况，正好是升序排列，比较迭代n-1次
15     最差情况，正好是降序排列，比较迭代1,2,...,n-1即 n(n-1)/2
16     使用两次嵌套循环，时间复杂度O(n^2)
17     稳定排序算法
18     使用在小规模数据比较
19     待优化：
20         如果比较操作耗时大的话，可以采用二分查找提高效率，即二分查找插入排序
21 
22 """
23 
24 m_list = [
25     [1,9,8,5,6,7,4,3,2],
26     [1,2,3,4,5,6,7,7,9],
27     [9,8,7,6,5,4,3,2,1],
28     [1,1,1,1,1,1,1,1,2]
29 ]
30 
31 nums = [0] + m_list[2]
32 print(m_list[2])
33 
34 sentinel,*origin = nums     #哨兵位，待比较数字
35 
36 count_swap = 0
37 
38 count_iter = 0
39 
40 length = len(nums)
41 
42 for i in range(2,length):   #从2开始
43     nums[0] = nums[i]       #放置哨兵
44     j = i - 1
45     count_iter += 1
46     if nums[j] > nums[0]:   #大数右移，找到插入位置
47         while nums[j] > nums[0]:
48             nums[j +1] = nums[j]    #依次右移
49             j -= 1
50             count_swap += 1
51         nums[j + 1] = nums[0]       #将哨兵插入，注意插入在右侧要+1
52 
53 print(nums,count_swap,count_iter)
54 
55 
56 
57 #以上代码执行结果如下:
58 [9, 8, 7, 6, 5, 4, 3, 2, 1]
59 [1, 1, 2, 3, 4, 5, 6, 7, 8, 9] 36 8