排序

插入排序

• 直接插入排序
  基本思想：把n个元素看成是有序表和无序表，每次往无序表中拿出一个元素，将它插入到有序表中适当的位置，使之成为新的有序表，冲入n-1次即可

• 希尔排序
  对于n个待排序的数列，取一个小于n的整数gap(步长)，将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。一趟完成后每一组元素都是元素的，不断减小gap重复这种操作，当gap=1时，整个数列都是有序的

  
  八种排序算法的时间复杂度、空间复杂度和稳定性