处理步骤

  • 选择第一个数据，和前面0个数据做对比，因为是第一个数据，则是当前数据中最小值，继续下一步
  • 选择第二个数据，和前面的1个数据做对比，如果当前数据小于前面的1个数据，则进行位置切换，继续下一步

  • 选择第n个数据，和前面的n-1个数据挨个作比较，如果当前元素大于第n个元素，则进行位置交换，否则遍历结束（因为前面的数据已经比较好了，是排好序的数据）

    演示过程

    插入排序.gif

    代码实现

  • python ```python

    选择排序

    from typing import Mapping from util import data,time_tools,test_sort

class InsertorSort: def init(self, data: list): assert len(data) > 0, “data length must > 0” self.__data = data

  1. def sort(self) -> list:
  2.     for i in range(len(self.__data)):
  3.         # 查看当前元素应该放在当前位置之前的哪个位置，包括当前位置
  4.         for j in range(1,i+1)[::-1]:
  5.             if self.__data[j]<self.__data[j-1]:
  6.                 self.__swap(j,j-1)
  7.             else:
  8.                 break
  10.     if test_sort(self.__data):
  11.         return self.__data
  13. # 交换数组中位置为 i 和 j 的数据
  14. def __swap(self, i: int, j: int):
  15.     self.__data[i], self.__data[j] = self.__data[j], self.__data[i] 
  2. - util
  3. ```python
  4. import random
  5. import time
  8. def data(num:int,max:int,is_sort=False)->list:
  9.     """
  10.     :param num: 数据量
  11.     :param max: 区间范围 0-max
  12.     :param is_sort: 数据是否已排序
  13.     :return: 生成的数据
  14.     """
  16.     #  数据生成
  17.     list_test = []
  18.     if is_sort:
  19.         for i in range(num):
  20.             list_test.append(i)
  21.     else:
  22.         for i in range(num):
  23.             list_test.append(random.randint(0, max))
  25.     return list_test
  28. def time_tools(tags:str,num:int):
  29.     # 装饰器定义 计算函数执行时间
  30.     def decorator(func):
  31.         def wrapper(*args, **kwargs):
  32.             start_time = time.time()
  33.             res = func(*args, **kwargs)
  34.             end_time = time.time() - start_time
  35.             print(f"算法:{tags} 数据量:{num} 执行时间为{end_time}")
  36.             return res
  37.         return wrapper
  38.     return decorator
  40. def test_sort(data:list)->bool:
  41.     #  测试排序结果是否正确 
  42.     for i in range(1,len(data)):
  43.         if data[i]<data[i-1]:
  44.             raise Exception("sort error ") 
  46.     return True
  • go ```go package mysort

type InsertorSort struct { // 待排序和排序后的数据 Data []int }

func (sort *InsertorSort) sort() {

  1. for i:=0;i<len(sort.Data);i++{
  2.     for j:=i;j-1>=0;j--{
  3.         if sort.Data[j]<sort.Data[j-1]{
  4.             sort.swap(j,j-1)
  5.         }else {
  6.             break
  7.         }
  8.     }
  9. }
  11. TestMySort(sort.Data)

}

// 交换data中 i j位置上的数据 func (sort *InsertorSort)swap(i int,j int) { sort.Data[i],sort.Data[j] = sort.Data[j],sort.Data[i] return

}

  1. <a name="t5eZj"></a>
  2. ## 时间复杂度分析
  3. O（n^2）<br />通过实际测试可以看到，随着排序数据的增加，其算法执行时间是呈平方倍增加，即如果样本从100到1000再到1000，可以看到执行时间分别会增加100倍，10的平方
  4. ```python
  5. # 算法:InsertorSort  数据量:100 执行时间为0.001994609832763672
  6. # 算法:InsertorSort  数据量:1000 执行时间为0.1107180118560791
  7. # 算法:InsertorSort  数据量:10000 执行时间为10.682084083557129

重要特性

插入排序在第二层循环中存在条件提前终止的可能，对于有序数组来讲，插入排序的时间复杂度最优可以达到O（n）
image.png

对于插入排序来讲，前面的数据一定是局部数据有序的，即前面的数据是已排好序，所以当遇到后面要插入的数据要大于之前排好序的数据的情况的时候可以提前终止判断。