Algorithms, Part I 4-Elementary sorts

Algorithms, Part I 4-Elementary sorts

HC_Plantern 48 2022-02-06

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$
  • 运行时间与输入无关

image.png

插入排序

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

复杂度分析

  • 平均 $\frac14N2$次比较,$\frac14N2$次交换

  • 最好情况:

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

    • 原序列从大到小排列:
    • $\frac12N2$次比较 $\frac12N2$次交换

代码实现

image.png

部分有序数组

定义逆序对

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

定义部分有序数组

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

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

命题

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

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

证明

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

Shell 排序

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

image.png

间隔选取

$3x+1$已经足够好

image.png

复杂度分析

  • 理论上最坏情况为$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];

找问题

image.png

凸包

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

应用

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

事实

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

葛立恒(Graham)扫描法

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

实现 CCW 判断逆时针旋转

使用有符号的面积

image.png

image.png