普林斯顿算法中级笔记4(基础算法,选择排序,插入排序,希尔排序)

基础算法

---

一些概念

• comparable:下面的算法实现用到了java中的一个业务排序概念。comparable类，简单来说，实现这个接口，实现里面的compare方法，网上有一揽子的相关解释。
• 一个静态方法：isSorted，这个方法用来判定一个数组是否已经完成排序。

private static boolean isSorted(Comparable[] a)
{
 for (int i = 1; i < a.length; i++)
 if (less(a[i], a[i-1])) return false;
 return true;
}

• 另一个静态方法，用来交换数组中两个元素的位置。

private static void exch(Comparable[] a, int i, int j)
{
 Comparable swap = a[i];
 a[i] = a[j];
 a[j] = swap;
}

• 再一个静态方法，用来比较元素大小

private static boolean less(Comparable v, Comparable w)
{ return v.compareTo(w) < 0; }

选择排序

排序原理:
1 从一组数中选择最小的那个，将它与第一个数字交换位置
2 从剩下的N-1个数字中选择最小的一个，将它与第二个数字交换位置
重复以上步骤
算法实现：

public class Selection
{
 public static void sort(Comparable[] a)
 {
 int N = a.length;
 for (int i = 0; i < N; i++)
 {
 int min = i;
 for (int j = i+1; j < N; j++)
 if (less(a[j], a[min]))
 min = j;
 exch(a, i, min);
 }
 }
}

算法分析：
每次选择的数组访问次数相加： (N– 1) + (N– 2) + ... + 1 ~ N²/2
该算法有两个特点：

1. 算法复杂度与原始数据的排序无关，无论是有序输入或是无序输入都需要遍历余下的数组。
2. 每一次交换的消耗很小

插入排序

排序原理：
遍历数组将第i个元素与之前的元素依次比较，然后把i放置到合适的位置，这个合适指的是，当它遇到第一个比它小的元素时所在的位置，因为每一次我们遍历时总能确定i前面所有的元素都是有序的。
算法实现：

public class Insertion
{
 public static void sort(Comparable[] a)
 {
 int N = a.length;
 for (int i = 0; i < N; i++)
 for (int j = i; j > 0; j--)
 if (less(a[j], a[j-1]))
 exch(a, j, j-1);
 else break;
 }
}

复杂度分析：
该算法平均需要1/4N²次比较，与1/4N²次交换（假设每个元素都需要移动1/2的长度）。
该算法有意思的地方在于，输入的数组顺序会影响最终的算法复杂度.
若输入数组本身就是正序的（我们希望排序后的样子），那么只需要N-1次比较，若输入数组是倒序的那么需要1/2N²次比较与1/2N²次交换。
影响插入排序的关键因素在于数组中有多少逆位（倒序元素的个数）。交换操作只需要会对逆位的地方进行操作。

希尔排序(shell sort 为毛不翻译成壳排序)

排序原理：
1 . 首先进行一定跨度的排序：
假设跨度为x，那么依照x对原始数组进行分组，分为：
0,x,2x,3x...
1,x+1,2x+1,3x+1...
...

屏幕快照 2018-08-02 下午4.27.40.png

而后对每个分组进行插入排序.

2. 将跨度x向小的方向变更，直到x=1。

为什么使用插入排序？

• 当x很大时，子数组很小，我们必不担心其复杂度
• 当x很小时，子数组很大，当时这是数组已经被部分排序，很适合插入排序。
  对希尔排序复杂度有很大影响的是x缩小规则。这里我们选用3x+1的缩小规则。即：1 4 13...，我也不晓得为毛选这个。

算法实现：这个算法的实现有些晦涩，但十分精妙，求学之路，渺渺无尽 ... 哀吾生之须臾，羡长江之无穷。

public class Shell {
    public static void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        //获取最大的跨度h
        while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, ...
        //然后对h跨度的子数组进行逐一插入排序，
        //假设我们h将原始 数组分成了n个子数组，那么个先比较第一个子数      
        //组的1与0，接下来下一个子数组的1,0。n个子数组遍历完全后，再 
        //继续比较第一个子数组的2,1 1,0(**插入排序**)
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                    exch(a, j, j - h);
            }
            h = h / 3;
        }
    }
}

当使用3x+1的规则时，该算法最差的算法复杂度为o(N^3/2)。

洗牌

算法目标：将原始数组随机的重新排列
算法原理：为每一个元素生成一个随机数，然后根据随机数进行排序。
算法复杂度取决于使用的排序算法。
另一种算法的原理：对于索引为i的元素在i与数组长度中间生成随机整数r，将r与i交换，这种算法的算法复杂度为N，是线性的。

实际应用：凸包

概念解释移步百度百科 凸包
问题：如何确定一个凸包的边界

• 首先，我们在平面上的点中取到，纵坐标最小的点:p，然后把所有的点按照该点到p的直线与横坐标之间的夹角的从大到小的顺序排列并命名。

  
  屏幕快照 2018-08-04 下午12.43.27.png
• 我们知道以下事实，如果该点是边界上的顶点，那么从起点p，依次连接所有顶点的路径，应该是完全逆时针的。由此我们可以确定处所有的顶点。
• 从点1 开始，遍历所有的点，依次连接，若路径中出现顺时针，则抛弃到时第二个点。

出现这种情况则抛弃点 3 出现这种情况则抛弃点 2.

• 如何判定三个点之间的路径是顺时针还是逆时针？
  T=(b_x − a_x )(c_y − a_y ) − (b_y − a_y )(c_x − a_x )
  T>0 : 逆时针
  T<0 : 顺时针
  证明可以使用向量相乘法，或者判定余弦正负的方法。