排序算法 9 P1:分类 排序算法可以分为内部排序和外部排序,在内存中进行的排序称为内部排序,当要排序的数据量很大时无法全部拷贝到内存,这时需要使用外存进行排序,这种排序称为外部排序。 内部排序包括比较排序和非比较排序,比较排序包括插入排序、选择排序、交换排序和归并排序,非比较排序包括计数排序、基数排序和桶排序。 其中插入排序又包括直接插入排序和希尔排序,选择排序包括直接选择排序和堆排序,交换排序包括冒泡排序和快速排序。 P2:直接插入排序 直接插入排序属于插入排序,是一种稳定的排序,平均/最差时间复杂度均为 O(n²),当元素基本有序时最好时间复杂度为 O(n),空间复杂度为 O(1)。 ...