Skip to content

Latest commit

 

History

History
196 lines (86 loc) · 4.1 KB

7.sort.md

File metadata and controls

196 lines (86 loc) · 4.1 KB

排序

稳定排序

插入排序

交换期望:

2个 $0.5 * 1 + 0.5 * 0=0.5$

3个 $\frac{1}{3} * 2 + \frac{1}{3} * 1=1$

4 $\frac{1}{4}*3+\frac{1}{4}*2+\frac{1}{4}*1=\frac{3}{2}$

所以可得平均交换期望$ \frac{n * (n - 1)}{4}$

冒泡排序

归并排序:外部排序

在合的时候会用到额外的存储空间,注意此存储空间只是向后追加数据就可以。不一定是内存中的数组,在硬盘里的文件也可以作为此空间。

所以对与一个经典的题:

电脑内存大小2GB,如何对一个40GB的文件进行排序?

就用20路归并排序每次对2GB排序,之后在硬盘进程合的过程,这也是归并排序为什么叫做外部排序-可以用外部的存储空间。

在每次对20个数据进行合的时候用小顶堆。

算法思想:分治----先处理左边,后处理右边。得到两边的信息后处理横跨左右两边的信息

非稳定排序

选择排序

每次从待排序区选择最小/大的放到已排序区的末尾

快速排序

选择基数+partition

从c++ STL中学习快速排序
  1. 单边递归法

    将传统的快排进行

    quick_sort(num, l, mid);
    quick_sort(num, mid + 1, r);

    变成单边递归,只递归左边,这就相当于减小了一半的开销-相当于减去了二叉树的右子树。右边用循环做。

    quick_sort(num, l, mid);
    r = mid - 1;//有点像二分哈哈
  2. 无监督partition法:

    即将快排递归函数的边界条件去掉用其他的方式替代,这样能避免它进入死循环

    少了个判断

  3. 三点取中法:

    partition时取base,取first, first + (last - first) / 2, last - 1中间的值

  4. 小数据规模

  5. 插入排序进行收尾

c++中的sort

混合排序:快速$(nlogn-n^2)$+堆$(nlogn)$

在递归quick_sort的时候记录一个深度阈值,如果超过这个阈值$(x \ nlogn) 一般取2 \ nlogn$就用堆排序。

这种情况下快排每次选数都选不到好的数,导致快排退化到$n^2$

实际实现的时候源码还将待排序序列分成了若干份,每份长__stl_threshold,即16

对于份之间即宏观上用混合排序,份内部用插入排序

Kaikeba OJ 103 104

计数排序

统计词频排序

以往我们的排序基本上都是对一个字段,即key-value对里的一个元素进行排序,叫多值排序

比如我们要对全国人的年龄排序,那么计数排序就很有应用场景了。因为年龄的值域非常有限(0~150)

基数排序

一部份思想借用了计数排序

先根据个位的信息处理,再根据十位的信息处理

比如对于序列13, 21, 11, 32, 31, 22, 21

处理步骤:

  1. 统计个位信息: 1-4个,2-2个,3-1个

    1 2 3
    4 2 1
    1. 对各位信息序列求个数前缀和:
1 2 3
4(个位为1的尾坐标为4, 以此类推) 6 7
  1. 从后向前扫描序列13, 21, 11, 32, 31, 22, 21

    21个位是1,放到1的尾坐标4的位置;22个位是2,放在2尾坐标6的位置,以此类推

    最后得到序列

    1 2 3 4 5 6 7
    21 11 31 21 32 22 13

    第一轮扫描完毕

  2. 基数排序可以保证数据的稳定性:

    31, 21为例.31还是在21前面,数字相对位置不变。

    之后对10位进行统计

    1 2 3
    2 5 7

    扫描序列21-1, 11, 31, 21-2, 32, 22, 13

    1 2 3 4 5 6 7
    11 13 21-1 21-2 22 31 32

    对于有很多位的还是依次处理每位。

拓扑排序

图本身没有含义,重要的是我们赋予它的含义

借助队列结构,存储点的入度,入度==0则点可以入队列了

kOJ 195