排序
排序的基本概念
算法稳定性：简单可以理解为相同的数值，排序前后相对位置有没有变。
又根据是否在内存再进行分为内部排序和外部排序
基本类型有：插入排序，交换排序，选择排序，归并排序，基数排序
插入排序
基本思想：将待排序的记录按顺序插入到已经排好的序列中。
直接插入排序
空间复杂: $O(1)$
时间复杂度: $O(n^2)$
是一种稳定算法, 适用于顺序存储和链式存储
折半插入排序
比较的时候使用二分法
空间复杂度: $O(1)$
时间效率: 比较次数为$O(nlog_2 n)$
时间复杂度: $O(n^2)$
是一种稳定算法, 只适用于顺序存储
希尔排序
取一个步长$d_i$,距离为$d_i$倍数的划为一组, 在区域内部进行插入排序, 后减少步长, 最后直至步长为1.
空间复杂度: $O(1)$
时间复杂度: $O(n)$
是一种不稳定算法, 适用于顺序存储
交换排序
根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置
冒泡排序
从后往前两两比较
空间复杂度: $O(1) $
时间复杂度: $O(n^2)$
是一种稳定算法, 适用于顺序存储
快速排序
目前最好的内部排序方法
首先选取一个元素作为枢纽,然后以此枢轴为界分为两个部分,左面小于该枢轴值,右面大于该枢轴值, 然后再对这两个部分分别递归的进行上述步骤
空间复杂度: 最好$O(n)$ 最坏$O(logn)$
时间复杂度: 最好$O(nlogn)$ 最坏$O(n^2)$
是一个不稳定算法
选择排序
简单选择排序
将表分为有序无序两部分, 每次从无序部分中选择一个合适的数放进有序部分
空间复杂度: $O(1)$
时间复杂度: $O(n^2)$
是一种不稳定算法
堆排序
空间复杂度: $O(1)$
时间效率: 建堆 $O(n)$, 调整 $O(nlog_2n)$
时间复杂度: $O(nlogn)$
不稳定算法
归并排序
选定相应元素合并成为一个新的有序表
空间复杂度: $O(n)$
时间复杂度: $O(nlog_2n)$
稳定的排序算法
基数排序
空间效率: 一趟需要辅助存储空间r 空间复杂度$O(r)$
时间效率: 需要d趟分配和收集 分配需要$O(n)$ 收集需要$O(r)$
时间复杂度: $O(d(n+r))$
是一种稳定的排序算法
易错点
- 基于比较的排序 比较次数至少为: $\lceil log_2(n!) \rceil$