排序算法稳定性
排序算法稳定性
排序算法稳定性：即相同的值排序后还是按照原有的次序
三个O(N)：
冒泡算法：可以实现稳定性，大数字往后冒泡的时候遇到相等的数不交换
选择排序：做不到稳定性
插入排序：可以实现稳定性，理由同冒泡，遇到相等的数不交换即可
三个O(N*logN)：
归并排序：可以实现稳定性，两边排好序merge时，遇到相等的数先拷贝左边的，再拷贝右边的
快速排序：做不到稳定性，partition（<，=，>）做不到稳定性（但有论文方法可以）
堆排序：做不到稳定性
建立大根堆时顺序就被打乱了
为什么讨论稳定性：现实业务需要稳定性，简单理解就是在已有顺序的基础上按别的关键字排序，可以保留之前的相对次序
工程排序算法
数组长度很长（数组长度大于60）：基础类型：快速排序，因为基础类型不用区分相同值；
自己定义的类：归并排序，自定义的class某关键字相同其他关键字可能不同
数组长度很短（数组长度小于60）：插入排序，因为插入排序常数项极低，小样本排序很快
排序问题补充
①归并排序额外空间复杂度可以做到O(1)，但不需要掌握，可以搜归并排序内部缓存法
②快排也可以做到稳定性，但很难不要掌握，可以搜01 stable sort
③一道题，奇数放数组左边，偶数放右边，还要求原始相对次序不变，这个问题有点坑，但还是01 stable sort
比较器
C++中重载运算符等价于定义比较器，不给比较器参数就用内存地址排序（自定义的类），或者报错，所以要添加比较器
基于比较的排序，重要的是排序策略，即比较器，可用于已有的结构TreeMap红黑树，PriorityQueue优先级队列（堆）等
桶排序、计数排序、基数排序
①非比较的排序，与实际数据状况有关，应用不多；
②时间复杂度O(N)，额外空间复杂度O(N)；
③稳定性
计数排序和基数排序是桶排序的具体实现
补充问题
这题没有用非比较排序，但是借助了桶的概念
用数组结构实现大小固定的队列和栈
按讲课的意思就是只要写插入删除操作
栈用单指针
队列用双指针，队尾end到底就回到开头，队头start记录要弹出的数，引入一个size表示长度记录标志位（加这个size代码会清晰很多）
例题
设计两个栈
题目三
队列实现栈
2个队列实现栈
栈实现队列
2个栈实现队列
push栈倒数据给pop满足两个行为：
①push栈倒数据给pop一次要倒完；
②pop栈有东西push栈一定不要倒
网友评论