插入类排序法

插入排序法是每次将一个待排序元素，按其元素值大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。

简单插入排序法（选择排序法）

基本思想：把n个待排序的元素看成是一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含另外n-1个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之称为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为n，而无序表为空，此时排序完成。

选择排序法：每遍历列表一遍就找出一个最小值，加入新列表；

Python实现：将数组元素按从小到 大的顺序排列。

# Finds the smallest value in an array
def findSmallest(arr):#用于找出最小值的函数
  # Stores the smallest value
  smallest = arr[0]
  # Stores the index of the smallest value
  smallest_index = 0
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest = arr[i]
      smallest_index = i
  return smallest_index
  #这里为何返回的是最小值的索引？

# Sort array
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      # Finds the smallest element in the array and adds it to the new array
      smallest = findSmallest(arr)
      #找出数组中最小的元素，并将其加入到新数组中去；
      newArr.append(arr.pop(smallest))
      #每次用了pop之后，会删掉之前找到的最小值？
  return newArr

print (selectionSort([5, 3, 6, 2, 10]))

输出：
[2, 3, 5, 6, 10]

希尔排序法

希尔排序（ShellSort）又称为“缩小增量排序”，它也是一种插入类排序的方法，但在时间效率上较简单插入排序有较大的改进。

基本思想：先取一个整数（称为增量）d1<n,把全部数据元素分成d1个组，所有距离为d1倍数的元素放在一组中，组成了一个子序列，对每个子序列分别进行简单插入排序。然后取d2<d1重复上述分组和排序工作，直到di=1，即所有记录在一组中为止。