顺序表中头部为空,表不为空,为什么不能用尾部不空来判定表满。
顺序表怎么定义的,顺序表不能在中间任何一个地方断开,否则叫什么顺序表
稳定性是指当待排序序列中有两个或两个以上相同的关键字时,排序前和排序后这些关键字的相对位置有没有改变,如果改变就说它不稳定,如果不改变就说它是稳定的。稳定性只是一个算法性质,并不能衡量一个算法的优劣。
排序类型 | 平均时间复杂度 | 平均空间复杂度 | 稳定性 | 是否支持顺序存储和链式存储 |
---|---|---|---|---|
直接插入法 | O(n2) | O(1) | 稳定 | 都支持 |
折半插入法 | O(n2) | O(1) | 稳定 | 顺序存储 |
希尔排序 | O(n2) | O(1) | 不稳定 | 顺序存储 |
简单选择排序 | O(n2) | O(1) | 不稳定 | 都支持 |
堆排序 | O(nlog2n) | O(1) | 不稳定 | 都支持 |
冒泡排序 | O(n2) | O(1) | 稳定 | 都支持 |
快速排序 | O(nlog2n) | O(log2n) | 不稳定 | 都支持 |
二路归并排序 | O(nlog2n) | O(n) | 稳定 | 都支持 |
基数排序 | O(d(n+rd)) | O(rd) | 稳定 | 都支持 |
复习时部分总结,有错误欢迎指正,立改,谢谢!