排序总结
|
时间复杂度 |
空间复杂度 |
是否能有稳定性 |
|
|
选择 |
O(N*N) |
O(1) |
|
|
冒泡 |
O(N*N) |
O(1) |
✔️ |
|
插入 |
O(N*N) |
O(1) |
✔️ |
|
归并 |
O(N*logN) |
O(N) |
✔️ |
|
快排(一般指3.0) |
O(N*logN) |
O(N*logN) |
|
|
堆 |
O(N*logN) |
O(1) |
|
基数排序作为不基于比较的排序，有稳定性
基础类型的排序一般排序用快排，因为其时间复杂度常数项更小，需要保持稳定定用归并，不想占用额外空间用堆排序
非基础类型的排序可以用归并，因为有稳定性
希尔排序：多轮插入排序
排序优化：
样本N较大时，先用快排划分为一个个N较小的样本，在小样本上使用插入排序（插入排序时间复杂度常数项极低）
哈希表查找 O(1) 有序表查找 O(logN)
笔试：不需要考虑空间复杂度
面试：空间复杂度尽量小
链表
基础题：
反转单向链表和双向链表 打印两链表公共部分
判断回文链表
笔试做法：快慢指针找到链表中间(链表长度为奇数/偶数 code不一样)，栈
面试做法：快慢指针找到链表中间，右半部分链表反转，判断回文，恢复链表
将单向链表按某值划分成左边小，中间相服务器托管网等，右边大的形式
笔试做法：每个节点放在数组里，数组做partition，把节点串起来
面试做法：六个变量，小于/等于/大于区域的头/尾，最后连起来(要注意三个区域是否为空)
复制链表，链表节点除有next指针外，还有一个rand指针，随机指向链表某个节点或为空
笔试做法：哈希表（key：老节点 value：新节点）
面试节点：把新节点串在老节点后面(再后面是下一个新节点)，省掉哈希表
服务器托管，北京服务器托管，服务器租用 http://服务器托管网www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: 【C++系列P5】‘类与对象‘-三部曲——[对象&特殊成员](3/3)一.const成员/成员函数二.匿名对象(即临时对象）三.static静态成员
前言 大家好吖，欢迎来到 YY 滴 C++系列 ，热烈欢迎！ 【 ‘类与对象’-三部曲】的大纲主要内容如下： 如标题所示，本章是【 ‘类与对象’-三部曲】三章中的第三章节——对象&成员章节，主要内容如下： 目录 一.const成员/成员函数 一.用c…
