4-Elementary sorts

引言

回调函数

为了能够对不同的数据类型进行排序（Double, String, File等）比较时调用compareTo()方法

交换次数

• 反对称：若$a \leq b$且$b \leq a$ 则 $a = b$
• 传递：若$a \leq b$且$b \leq c$ 则 $a \leq c$
• 完全：$a \leq b$ 或 $ b \leq a$

Comparable API

实现 compareTo() 那么 v.comnpareTo(w)

• 是全序关系
• 如果$v$小于、等于或大于$w$，则分别返回负数、零和正数
• 异常情况抛出exception

选择排序

从未排序的元素中选择一个最小的与当前指针指向的元素交换

复杂度分析

• 比较次数：$(N– 1) + (N– 2) + … + 1 + 0 $ ~ $ N^2 / 2$
• 交换次数：$N$
• 运行时间与输入无关

插入排序

从未排序的序列中选择第一个元素，从后往前依次比较并交换，直到到达最前面或者找到更小的元素

复杂度分析

• 平均 $\frac14N^2$次比较，$\frac14N^2$次交换

• 最好情况：

  • 原序列已经从小到大排好序
  • $N-1$次比较$N$次交换

• 最坏情况

  • 原序列从大到小排列：
  • $\frac12N^2$次比较 $\frac12N^2$次交换

代码实现

部分有序数组

定义逆序对

一个逆序对是数组中乱序的关键值对

定义部分有序数组

如果一个数组的逆序对数量是线性的，或者说 $逆序对数量\leq cN$，那么这个数组是部分有序的

对于部分有序数组，插入排序的时间复杂度是线性的

命题

$交换次数 = 逆序对数量$

$逆序对数量 \leq 比较次数 \leq (N-1)$

证明

每次交换都改变了两个顺序颠倒的元素的位置，相当于减少了一对倒置，当倒置数量为
0 时，排序就完成了。每次交换都对应着一次比较，且 1 到 N-1 之间的每个 i 都可能需要一次
额外的比较（在 a[i] 没有达到数组的左端时）。

Shell 排序

以一定的间隔进行排序，缩小间隔直到为1

间隔选取

$3x+1$已经足够好

复杂度分析

• 理论上最坏情况为$O(N^{\frac32})$
• 实际上接近 $cNlogN$

代码实现

public class Shell { 
    public static void sort(Comparable[] a) { // 将a[]按升序排列
         int N = a.length; 
         int h = 1; 
         while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ... 

         while (h >= 1) { // 将数组变为h有序
             for (int i = h; i < N; i++) { // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中
             for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
                exch(a, j, j-h);
            }

         h = h/3;
    }
}

洗牌算法

如何将一副牌随机打乱呢？Shuffle 洗牌算法是一个用来将一个有限集合生成一个随机排列的算法（数组随机排序）。具体做法：

for i from n−1 to 1 do:
    j ← random integer such that 0 ≤ j ≤ i; 
    exchange a[j] and a[i];

找问题

凸包

N个点的集合的凸包就是周长最小的能把这些点围起来的点的凸多边形

应用

• 找到绕开障碍物的最短路径
• 
• 从N个点的集合中找到距离最远的一对点
• 

事实

1. 可以只通过逆时针转弯来走遍闭包
2. 原点与凸包的顶点连成的向量，极角递增

葛立恒（Graham）扫描法

• 选择y坐标最小的点p
• 以p为起点，将p与各点按照极角大小排序
• 按照排序连接点，如果产生顺时针旋转，那么就舍弃这个点
• 

实现 CCW 判断逆时针旋转

使用有符号的面积