左神初级算法课程第三讲笔记-排序算法稳定性

排序算法稳定性

排序算法稳定性

排序算法稳定性：即相同的值排序后还是按照原有的次序

三个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栈一定不要倒