站内链接:

Introduction

插入排序, 将新的未排序值插入到已排序的队列中, 重复以上流程. 插入排序分类如下:

  • 直接插入排序: 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入.插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间.
  • 希尔排序: 缩小增量排序, 记录按下标的一定增量分组，对每组使用直接插入排序算法排序, 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止.

直接插入排序

Anaylysis

本质上，一种比较类-非线性-插入类-排序. 民主自由的制度，不到最后，谁都不能确定村长是谁！(其实吧，结果还不是一样，选择的方向不同而已). 对比过程如下:

1
2
3
4
5
6
7
你，就是你，你身高多少?185?
比SB1高啊.....
  SB1，你往后面走一步，index=SB1之前的位置
比SB2高啊....
  SB2，你往后走一步，index=SB2之前的位置
嘿嘿，没有SB3高！
  滚到index里面站着吧

插入排序的最优性能:

1
2
3
4
基本有序，此时做的操作基本为0
选择排序就不是咯，还是的选择出最大值
交换排序也是，但是吧
所以，希尔排序才会以插入排序为基础

insertsort

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def insertSort(list1):
    """insertSort

    :param list1:
    """
    list_len = len(list1)

    # 1，从改列的第二个元素开始
    for i in range(1, list_len):
        # 2，记住当前欲插入的元素为tmp
        tmp = list1[i]
        # 3，空闲位置
        index = i
        # 4，从前面的已排序序列的尾部开始往前遍历，递减比较
        for j in range(i - 1, -1, -1):
            if tmp < list1[j]:
                list1[j + 1] = list1[j]
                index = j
            else:
                break

        list1[index] = tmp

    return list1

希尔排序

Analysis

本质上，一种比较类-非线性-插入类-改进的插入-排序, 什么?你说插入排序最优和最差的区别好大?难道说?

  • 最优: 整个队列基本有序，此时 O(n)
  • 最差:O(n*n)

最优时的特征: 越是基本有序，比较和移动的次数越小, n 越小，O(n*n)越小哦(二分思维), 这就是希尔排序的提出原因, 因为基本插入排序每次移动一个一位, 所以进行了改进. 希尔希尔来临:

1
2
3
a. 初期使用大跨度的间隔比较, 让记录跳跃式的接近它的排序位置.
b. 增量减小, 进行小范围的记录跳跃式排序.
c. 最后进行最后一次n=1, 完整的insert sort(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
原始字符串: 13, 14, 94, 33, 82, 25, 59,  ..., 25, 39, 10
如果step = 5，那么就有5列，对每一列进行插入排序:
    13 14 94 33 82
    25 59 94 65 23
    45 27 73 25 39
    10
    ==============
    10 14 73 25 23
    13 27 94 33 39
    25 59 94 65 82
    45
如果step = 3, 则存在3列
    10 14 73
    25 23 13
    27 94 33
    39 25 59
    94 65 82
    45
    =====
    10 14 13
    25 23 33
    27 25 59
    39 65 73
    45 94 82
    94
最后开始step=1, 进行简单插入排序, 此时大部分数据都是有序的, 理想情况下就是一直插入末尾.

Example

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
def shellSort(list1):
    """shellSort

    :param list1:
    """
    list_len = len(list1)
    step = int(round(list_len / 2))

    while step > 0:
        # 注意，下面的排序思路完全仿照insertsort中的写法
        for i in range(step, list_len):
            # 第i/step列的第二位元素，之后变为第i/step + 1列，...
            temp = list1[i]
            index = i
            for j in range(i - step, - 1, -step):
                if list1[j] > temp:
                    list1[j + step] = list1[j]
                    index = j
                else:
                    break
            list1[index] = temp

        step = int(round(step / 2))

    return list1