排序算法之插入排序（python实现）_python插入排序

数据结构排序算法之插入排序（python实现）

---

---

前言

插入排序的基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入位置。
即边插入边排序，保证子序列中随时都是排好序的。

插入排序的种类：
顺序法定位插入位置——直接插入排序
二分法定位插入位置——二分插入排序
缩小增量多遍插入排序——希尔排序

---

一、直接插入排序

1.基本思想

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从前向后或从后向前扫描，找到相应位置并插入。

动图如下：

2.代码实现

代码如下（示例）：

items = [10, 4, 5, 1, 3, 9, 7]
def s_insertSort(items):
    item = items.copy()
    number = len(items)
    for i in range(0,number):
        if i != 0:		# i相当于哨兵，记录每次插入到第几个数，即前i-1个数已经有序，这里判定是第一次插入，不需要交换位置，所以写了一个非的条件判定
            for j in range(0,i):	# 从前i-1个有序数列里查找，并完成插入
                if item[j] > item[i]:
                    item[j],item[i] = item[i],item[j]	# 在前几篇博客里对于数值的交换，我们设置了一个暂存变量temp，以此来完成两个数的交换，这是致敬C语言的数据结构代码实现，python实现两个数的交换更简单，如代码所示
        #print(item)    # 此处可打印每一遍的排序详情
    return item
    
print('选择排序已完成！',selectionSort(items))		# 选择排序已完成！ [1, 3, 4, 5, 7, 9, 10]

print(items)	# [10, 4, 5, 1, 3, 9, 7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(n2)；
空间复杂度：O(1)；
稳定性：稳定；
应用场景：序列接近有序或者元素个数比较少

---

二、折半插入排序

1.基本思想

首先确定好low、mid、high 3个位置，一般情况下中间位置mid = (low + high)/2。
（1）搜索过程从中间元素开始，若中间元素刚好等于所要查找的元素则返回查找元素下标，查找结束。
（2）若中间元素小于所要查找的元素，则查找元素存在于中间元素的右边，并重新确定low的位置，low = mid+1
（3）若中间元素大于所要查找的元素，则查找元素存在于中间元素的左边，并重新确定high的位置，high = mid -1
（4）若low>high,则表中并没有所要查找的元素

2.代码实现

代码如下（示例）：

def Binary_insertSort(items):
    item = items.copy()
    number = len(item)
    for i in range(1,number):       # 在直接插入排序中代码中，使用if i != 0 的判定对首次插入，这里是不同的方法
        temp = item[i]      # 临时变量将要插入的数字保存，避免后面被覆盖掉
        low = 0             # 判定low 、high、mid
        high = i-1
        while low <= high:
            mid = int((low + high) / 2)
            if temp < item[mid]:
                high = mid -1
            else:
                low = mid + 1
        for j in range(i-1,high,-1):    # 因为临时变量保存了第i个值，因此将前面直到high的值依次向后移动，覆盖也没关系
            item[j+1] = item[j]
        item[high+1] = temp     # 移动完成后插入i的值
        #print(item)        # 打印每轮排序的结果

    return item

print('选择排序已完成！',Binary_insertSort(items))		# 选择排序已完成！ [1, 3, 4, 5, 7, 9, 10]

print(items)	# [10, 4, 5, 1, 3, 9, 7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：折半插入排序减少了比较元素的次数，其移动次数与直接插入排序是一样的，所以其时间复杂度与其是一样的。最好时间复杂度为O(nlog2n)，而最坏情况下，最坏时间复杂度为O(n2)，而考虑平均情况下，折半插入排序的时间复杂度仍为O(n2)；
空间复杂度：与直接插入排序一样，空间复杂度仍为O(1)；
稳定性：稳定
应用场景：折半插入排序只适用于顺序表，不适用于链表

---

三、希尔排序

1.基本思想

设待排序元素有n个，首先取一个整数gap<n作为间隔，将全部元素分为gap组，所有距离为gap的元素都在同一个组里，然后对每一个组都进行插入排序。然后缩小增量，直到gap==1的时候整个序列都会变成有序的。

动图如下：

2.代码实现

代码如下（示例）：

items = [ 10,4, 5, 1, 3, 9, 7, 8, 6, 11, 2, 14, 13]         # 希尔排序数组长一点效果更直观，所以不用平时的那个数列
def ShellinsertSort(items):
    item = items.copy()
    number = len(item)
    gap = number        # 增量 
    while gap > 1:
        gap = int(gap / 2)      # 增量要减小，直到增减为1 此处有两种方法，还有一种是gap/ + 1，无论哪种最后gap都等于1
        # print(gap)
        for i in range(gap,number):
            pos = i - gap       # 有序区的最后一个元素
            # print(pos)
            temp = item[i]
            while pos >= 0 and item[pos] > temp:
                item[pos + gap] = item[pos]  
                pos -= gap
            item[pos + gap] = temp
        print(item)     # 打印每一轮排序结果
    
    return item
print('每一轮打印结果如下：')
print('选择排序已完成！',ShellinsertSort(items))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

每一轮打印结果如下：
[7, 4, 5, 1, 2, 9, 10, 8, 6, 11, 3, 14, 13]
[1, 2, 5, 7, 3, 6, 10, 4, 9, 11, 8, 14, 13]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14]
选择排序已完成！ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14]

希尔排序的时间复杂度：不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，但是有一个大概的范围：时间复杂度大概为O(N1.3)略低于O(N*logN)。
空间复杂度：O(1)。
稳定性：不稳定。