排序

#排序

算法稳定性：关键字相同的元素，排序后元素的相对位置发生改变，则称算法不稳定
分类：

• 内部排序：数据全在内存中（关注时间、空间复杂度）
• 外部排序：数据太多无法全部放入内存（关注磁盘IO）

[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html]可视化算法网站

排序理解
排序流程
排序诗

冒泡排序

属于交换排序的一种
交换排序：

1. 冒泡排序
2. 快速排序
   思想：从后往前，两两比较，若为逆序，交换为顺序，每一轮会把最小的元素留在最前面，从前往后则是把最大的元素留在后面，若一趟排序没有发生交换，说明整体已经有序，逆序才交换，因此具有稳定性
   稳定性：有

复杂度分析：
空间：O(1)
时间：

• 最好：O(n)
• 最坏：O($n^2$)
  是否适用链表：是（从前往后冒泡）

插入排序

思想：把待排序的插入到排好序的序列中，比它更大的全部后移，大小相等的不动，保证了算法稳定性。第一轮把第一个元素作为排好的序列。
稳定性：有
实现方式：

1. 不带哨兵，引入临时变量
2. 把0号元素作为哨兵，不引入临时变量,带哨兵的实现方式可以不用判断j是否合法
3. 优化：折半插入排序，折半查找为了找到待插入的位置，并没有改变时间复杂度
   复杂度分析：
   空间:O(1)
   时间:n个元素 n-1趟处理

• 最好O(n)：原本有序
• 最坏O($n^2$)：原本逆序
• 平均O($n^2$)
  应用场景：待排序列基本有序

希尔排序

先追求表中部分有序，再逐渐逼近全局有序
思想：先把待排表分割成增量为d的子表，对各个子表进行直接插入排序，缩小增量d直到d=1,希尔本人建议增量d每次缩小一半
稳定性：不稳定 如65 49 49 d=2第一趟就破坏了稳定性
复杂度分析：涉及数学上未解决的难题，时间复杂度分析起来比较困难
最坏（d=1像插入排序一样）：$O(n^2)$
最好：n在某个特定范围时可达到$O(n^{1.3})$
空间：O(1)
是否适用链表：否

• 归并排序

快速排序

属于交换排序的一种
思想：表中选一个基准pivot，low指针指向最左，high指针指向最右，移动指针把待排序列扫描一遍把比它小的放low左边，比它大或等于的放high的右边，low和high相遇后确定基准元素的位置，再对基准元素左右的两个子表进行划分,代码实现可以先划分，再递归调用快排
稳定性：不稳定
复杂度分析：
时间：
最好：O(n$\times$递归层数)=$O(n\times lo{g}_{2}n$)
最坏：$O(n^2$)
平均：$O(n\times lo{g}_{2}n$)
空间：O(递归层数)
最好：$O(lo{g}_{2}n)$
最坏：$O(n)$

递归层数可以转化为二叉树的高度

简单选择排序

属于选择排序
思想：每一趟排序再待排元素中选择关键字最小（或最大）的元素加入有序子序列
只需要（一定要）进行n-1趟处理,无论序列什么样
稳定性：不稳定 eg.2 2 1
空间复杂度：O(1)
时间复杂度：O($n^2$)

堆排序

属于选择排序
基于一种叫堆的数据结构：顺序存储的完全二叉树
数据结构-堆
大根堆：所有节点都要大于它的左右孩子节点
小根堆：所有节点都要小于它的左右孩子节点
建立大根堆思路：检查所有非终端节点（非叶子节点），顺序存储$1\sim \frac{n}{2}$，检查结点是否满足根>左\右,如果不满足，把根节点和左右节点中最大的那个互换，若元素互换破坏了下一级的堆，则采用相同的方法继续向下调整（小元素下坠的处理）
基于大根堆排序：堆顶元素和待排元素（i>$\frac{n}{2}$）最后一个进行进行交换，将待排元素重新调整成大根堆，调用调整堆的函数时把长度len-1(因为顺序存储，最后一个已经排好了)，循环往复，n个元素进行n-1趟排序，得到递增序列
稳定性：不稳定 eg.2 1 2
时间复杂度：计算过程很复杂，建堆的对比次数不超过4n，建堆时间复杂度=O(n),涵盖了二叉树的内容
O(n)+O($lo{g}_{2}n$) =O（$lo{g}_{2}n$）

在堆中插入新元素：在堆底插入新元素，然后新元素不断上升到无法上升即可
在堆中删除元素：用堆底元素代替它，让堆底元素不断下坠
对比关键字的次数也是一个考点

归并排序（merge）

把两个有序的序列合二为一（二路归并）如果有n个有序序列称为n路归并
二路归并思路：两个指针，分别指向两个有序（假设为递增）序列的头部，每次比较两指针指向的值大小，把更小的那个放到新的序列里，相等时优先放一边的
思路：把每个元素作为有序序列进行二路归并，下一轮再对有序序列进行二路归并
归并树:形态上就是一颗倒立的二叉树
稳定性：稳定
时间复杂度：O(nlogn)
空间复杂度：O(n)

基数排序

思路： 依据个位十位百位的这个顺序进行排序、定义10个队列，把每轮的那一位数对应的值，把那个数放到对应那个值的队列里，然后先收集更小的再收集最大的收集后进行下一轮

需要r个辅助队列，共d趟分配、收集
稳定性：有（因为队列先进先出）基你太稳？？？
时间复杂度：O(d(n+r))
空间复杂度：O(r)
不是基于比较的排序
几乎不考代码
应用：也可以排年龄按年月日，如果拆为d组，d的值较小，r的值较小，数据元素个数n特别大，时间复杂度远小于其它排序(O($n^2$),O(nlogn))

• 计数排序
• 桶排序

外部排序

数据元素太多，无法一次把所有数据读入内存进行排序
主存与磁盘之间以块为单位进行读写
使用归并排序

• 每次读入两个块的内容，放到输入缓冲区里，进行内部排序，排序好了写回磁盘
• 构造初始归并段
• 进行归并排序 输入缓冲区空了立即从归并段中补充下一个块的内容， 输出缓冲区满了立即写回磁盘
  时间开销=读写外存的时间+内部排序时间+内部归并时间
  进行优化，减少归并趟数，使用多路归并，在内存中分配多个输入缓冲区
  这时就增加了归并段的大小，同时减少了归并次数

k路平衡归并 ？平衡？

败者树：可视为完全二叉树
增加了多路（k路）排序的路数，需要比较找出最小关键字的比较次数增加变成了（k-1）次，
使用败者树只需要$lo{g}_{2}k$向上取整次比较