内部排序：指待排序记录全部存放在内存中排序的过程。
外部排序：指待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的过程。
插入排序
1.直接插入排序
先将序列中的第一个记录看成一个有序列，然后从第二个记录开始，逐个进行插入，直至整个序列有序，排序过程为n-1躺插入。
- 时间效率：因为在最坏情况下，所有元素的比较次数总和为（0+1+...+n-1)—>O(n的平方），时间复杂度O(n的平方）。
- 空间效率：仅占用1个缓冲单元—O(1)
-
算法的稳定性：稳定
2、希尔排序
示意图
选择排序
每一次从待排序的数据元素中选出最小的一个元素，存放在已排序列的后面，直到全部待排序的数据元素排完。
- 优点：实现简单
- 缺点：每趟只能确定一个元素，表长为n时需要n-1趟
- 前提：顺序存储结构
1、直接选择排序
在所有记录中选出最小的记录，把它与第一个记录交换，然后在剩余的记录内选出最小的记录与第二个记录交换...依次类推。
示意图
2、堆排序
示意图
堆排序的最坏时间复杂度为O(n倍的log以2为底的n次方），堆排序平均性能接近最坏性能。
堆排序的辅助空间为O(1)。
交换排序
1、冒泡排序
- 时间效率：O(n的平方)
- 空间效率：O(1)
- 稳定性：稳定
2、快速排序
- 优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别
示意图
快速排序最坏时间复杂度O(n的平方），最好时间复杂度为O(n倍的log以2为底的n次方）
归并排序
可以把一个长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两归并，得到n/2个长度为2的有序子序列；再做两两归并，如此重复，直到最后得到一个长度为n的有序序列。
示意图
时间效率：O(nLog以2为底的n次方)
空间效率：O(n)
稳定性：稳定
算法复杂性比较
排序算法时间复杂度表
网友评论