八大排序算法时间复杂度和空间复杂度对比与实现
发布时间：2024-02-02 19:30
八大排序算法时间复杂度和空间复杂度对比与实现
算法时间复杂度和空间复杂度对比
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
八大排序就是内部排序。
- 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
- 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；
- 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
八大排序算法原理与实现
- 插入排序
- 希尔排序
- 选择排序
- 堆排序
- 冒泡排序
- 快速排序
- 归并排序
- 基数排序