## 插入排序

### 直接插入排序

原理：

• 在未排序序列中，构建一个子排序序列，直至全部数据排序完成
• 待排序的数，插入已经排序的序列中的合适位置
• 增加一个哨兵，放入待比较值，让它和后面已经排好序的序列比较，找到合适的切入点

举例：

初始值：[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

思路：

• 增加一个哨兵位，每躺将待比较的值放入其中
• 哨兵依次和带比较数的前一个比较，大数向右移动，找到哨兵中的值要插入的位置
• 每一轮结束，得到一个从开始到待比较数位置的一个有序序列

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

nums = [0] + m_list[2] # 添加哨兵位
print(nums[1:])

length = len(nums)
count_move = 0
for i in range(2, length): # 跳过哨兵和第一个元素，从第二个元素开始
    nums[0] = nums[i]      # 将带比较值放入哨兵位
    j = i - 1
    if nums[j] > nums[0]:  # 大数右移，找到插入位置
        while nums[j] > nums[0]:
            nums[j+1] = nums[j] # 右移
            j -= 1         # 继续向左比较
            count_move += 1
        nums[j+1] = nums[0] # 插入哨兵，j本是合适位置，但在退出循环之前被-1(19行)，所以要加回来

print(nums[1:], '数据移动的次数：{}'.format(count_move), sep='\n')

总结：

• 插入排序特点：
  • 最好情况，正好是升序排列，比较迭代n-1次
  • 最差情况，正好是降序排列，比较迭代1,2,...,n-1即 n(n-1)/2，同样也是数据移动的次数，数据移动非常之多
  • 使用两次嵌套循环，时间复杂度O(n^2)
  • 是稳定排序算法
  • 用在小规模数据比较

什么是稳定排序算法

​ 待排序序列R中有两个元素相等，即R[i] = R[j]，且i < j，那么排序之后这两个元素的先后顺序不变，这种排序算法就称做稳定排序。要判断哪些算法是稳定排序，拿[1, 1, 2]来测试就行

• 待优化：
  如果比较操作耗时大的话，可以采用二分查找提高效率，即二分查找插入排序

# 选择排序

## 简单选择排序

简单选择排序属于选择排序的一种算法，原理是两两比较大小，找出极值（极大或者极小）放在固定的位置，这个固定的位置一般指的是某一端，结果可以是升序也可以是降序。

降序

n个数从左到右，开始遍历

第一轮：索引从0开始到n-1，两两相依比较，记录大值索引，此轮所有数比较完毕，将大数和索引0数交换，如果大数就是索引0，不交换。

第二轮：从索引1开始比较，找到最大值，将其和索引1位置交换，如果他就在索引1位置则位置不交换。

以此类推，每次左边都会固定下一个大数。

升序

和降序相反

简单选择排序的实现

m_list = [
    [3, 2, 7, 1, 1, 5, 8, 5, 2],
    [9, 1, 8, 8, 5, 3, 8, 8, 9],
    [7, 9, 8, 6, 3, 8, 9, 7, 1]
]

nums = m_list[2]
print(nums)

length = len(nums)
count_iter = 0 # 迭代的次数
count_swap = 0 # 元素位置交换的次数
for i in range(length):
    maxindex = i # 初始化最大值索引指针
    for j in range(i + 1, length):
        count_iter += 1
        if nums[j] > nums[maxindex]: # 最大值指针指向的值与无序区的元素一一比较，maxindex永远指向更大的值；遍历完一遍，就能找到无序区种的最大值了
            maxindex = j
    if i != maxindex: # 判定最大值指针是否移动过，没移动过就说明i 比无序区里面的数字都大了
        nums[i], nums[maxindex] = nums[maxindex], nums[i] # 将无序区选出来的最大值放在有序区的边界
        count_swap += 1
print(nums, count_iter, count_swap, sep='\n')


#运行结果
[7, 9, 8, 6, 3, 8, 9, 7, 1]
[9, 9, 8, 8, 7, 7, 6, 3, 1]
36
6

## 简单选择排序的优化--二元选择排序

同时选择固定左边最小值和右边最大值

优点：一次迭代，就找出最大&最小值，这样无序区范围再一次迭代就被再次缩小了 ，<font color=red>需要迭代的次数就少了</font>

m_list = [
    [3, 2, 7, 1, 1, 5, 8, 5, 2],
    [9, 1, 8, 8, 5, 3, 8, 8, 9],
    [7, 9, 8, 6, 3, 8, 9, 7, 1],
    [1, 1, 1, 1, 2, 1, 1, 1, 1]
]

nums = m_list[3]
print(nums)
length = len(nums)
count_iter = 0
count_swap = 0

for i in range(length // 2):
    '''
    为什么是迭代(length // 2) 次就能完成排序了？
    因为一次迭代就搞定了两个数，
    如果length是偶数，那么len//2次就能确定len个元素的顺序
    如果length是基数，那么len//2次就能确定（len-1）个元素的顺序，因为len//2是向下取整，len//2*2 + 1 = len，
    至于最后剩下那个数就是中间数，因为他左右两边的顺序都是好的了
    '''
    maxindex = i # 初始化最大值指针，指向无序区最左的元素，假定他为无序区里的最大值
    minindex = -i - 1 # 初始化最小值指针，指向无序区最右的元素，假定他为无序区里的最小值
    minorigin = length + minindex # 无序区初始化最小值的正索引，同时也是无序区最右的元素的正索引
    for j in range(i+1, length-i): # 遍历无序区除了一个极值外的数，range(i+1, minorigin+1) => range(i+1, length+minindex+1) => range(i+1, length+(-i - 1)+1)
        count_iter += 1
        if nums[j] > nums[maxindex]: # 找出无序区得最大值，方法是，两两比较，maxindex总是指向更大值的索引，比完一圈就找到最大值索引了
            maxindex = j
        if nums[-j - 1] < nums[minindex]: # 找出无序区得最小值，方法是，两两比较，minindex总是指向更小值的索引，比完一圈就找到最小值索引了
            minindex = -j - 1
    minindex = length + minindex # minindex在前面一直用的是负索引，这里转成正索引更方便
    if i != maxindex:
        nums[i], nums[maxindex] = nums[maxindex], nums[i] # 如果最大值就是无序区最左的元素，那就不用交换位置啦
        count_swap += 1
        if i == minindex: # 因为上面的swap操作使得元素的位置发生变化，如果被移位的i刚好是minindex，那么要更新minindex，因为我们追踪的是值，不是索引
            minindex = maxindex
    if minindex != minorigin: # 如果最小值就是无序区最右的元素，那就不用交换位置啦
        nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
        count_swap += 1

print(nums, count_iter, count_swap, sep='\n')



#运行结果
[7, 9, 8, 6, 3, 8, 9, 7, 1]
[9, 9, 8, 8, 7, 7, 6, 3, 1]
20
6

可以优化的地方：

如果一次迭代中，找出来的极大值和极小值的值相等，说明比较序列元素全部相等，没有继续调整顺序的必要了。

m_list = [
    [3, 2, 7, 1, 1, 5, 8, 5, 2],
    [9, 1, 8, 8, 5, 3, 8, 8, 9],
    [7, 9, 8, 6, 3, 8, 9, 7, 1],
    [1, 1, 1, 1, 2, 1, 1, 1, 1]
]

nums = m_list[3]
print(nums)
length = len(nums)
count_iter = 0
count_swap = 0

for i in range(length // 2):
    maxindex = i 
    minindex = -i - 1 
    minorigin = length + minindex 
    for j in range(i+1, length-i):
        count_iter += 1
        if nums[j] > nums[maxindex]: 
            maxindex = j
        if nums[-j - 1] < nums[minindex]:
            minindex = -j - 1
    if nums[maxindex] == nums[minindex]: break  #优化之处
    minindex = length + minindex 
    if i != maxindex:
        nums[i], nums[maxindex] = nums[maxindex], nums[i] 
        count_swap += 1
        if i == minindex: 
            minindex = maxindex
    if minindex != minorigin: 
        nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
        count_swap += 1

print(nums, count_iter, count_swap, sep='\n')

想[1, 1, 1, 1, 1, 1, 1, 1, 2]这种情况，第一轮找到的最大值索引是8，最小值索引是-2，如果按照上面的算法，会交换两次，两个最小值1交换就是无用功，所以增加一个判断。

说起来都是前面极大值交换位置引起的，minorigin索引指向的值被交换位置也不影响，因为minindex已经是无序区中最小的，换谁来当minorigin都一样，minindex都是最小，但是如果宝贝被换过的minorigin对应的值就有可能和minindex相同（原始的minorigin和minindex肯定是不同的，因为上面选minindex有做判断，minorigin被置换的话就不一样了），调换位置就是徒劳的。

m_list = [
    [3, 2, 7, 1, 1, 5, 8, 5, 2],
    [9, 1, 8, 8, 5, 3, 8, 8, 9],
    [7, 9, 8, 6, 3, 8, 9, 7, 1],
    [1, 1, 1, 1, 2, 1, 1, 1, 1]
]

nums = m_list[3]
print(nums)
length = len(nums)
count_iter = 0
count_swap = 0

for i in range(length // 2):
    maxindex = i 
    minindex = -i - 1 
    minorigin = length + minindex 
    for j in range(i+1, length-i):
        count_iter += 1
        if nums[j] > nums[maxindex]: 
            maxindex = j
        if nums[-j - 1] < nums[minindex]:
            minindex = -j - 1
    if nums[maxindex] == nums[minindex]: break  #优化1
    minindex = length + minindex 
    if i != maxindex:
        nums[i], nums[maxindex] = nums[maxindex], nums[i] 
        count_swap += 1
        if i == minindex: 
            minindex = maxindex
    if minindex != minorigin and nums[minorigin]!=nums[minindex]:  #优化2
        nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
        count_swap += 1

print(nums, count_iter, count_swap, sep='\n')

## 总结

• 简单选择排序需要数据一轮轮的比较，并在每一轮中发现机值
• 没有办法知道当前轮是否已经达到排序要求，但是可以知道极值是否在目标索引上
• 遍历次数：1，2，3，...，n-1之和，即n(n-1)/2
• 时间复杂度O(n**2)
• 减少了交换次数，提高了效率，性能率好过冒泡法