基础算法
一些概念
- 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 ~ N2/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/4N2次比较,与1/4N2次交换(假设每个元素都需要移动1/2的长度)。
该算法有意思的地方在于,输入的数组顺序会影响最终的算法复杂度.
若输入数组本身就是正序的(我们希望排序后的样子),那么只需要N-1次比较,若输入数组是倒序的那么需要1/2N2次比较与1/2N2次交换。
影响插入排序的关键因素在于数组中有多少逆位(倒序元素的个数)。交换操作只需要会对逆位的地方进行操作。
希尔排序(shell sort 为毛不翻译成壳排序)
排序原理:
1 . 首先进行一定跨度的排序:
假设跨度为x,那么依照x对原始数组进行分组,分为:
0,x,2x,3x...
1,x+1,2x+1,3x+1...
...
而后对每个分组进行插入排序.
- 将跨度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(N3/2)。
洗牌
算法目标:将原始数组随机的重新排列
算法原理:为每一个元素生成一个随机数,然后根据随机数进行排序。
算法复杂度取决于使用的排序算法。
另一种算法的原理:对于索引为i的元素在i与数组长度中间生成随机整数r,将r与i交换,这种算法的算法复杂度为N,是线性的。
实际应用:凸包
概念解释移步百度百科 凸包
问题:如何确定一个凸包的边界
-
首先,我们在平面上的点中取到,纵坐标最小的点:p,然后把所有的点按照该点到p的直线与横坐标之间的夹角的从大到小的顺序排列并命名。
- 我们知道以下事实,如果该点是边界上的顶点,那么从起点p,依次连接所有顶点的路径,应该是完全逆时针的。由此我们可以确定处所有的顶点。
- 从点1 开始,遍历所有的点,依次连接,若路径中出现顺时针,则抛弃到时第二个点。
- 如何判定三个点之间的路径是顺时针还是逆时针?
T=(bx − ax )(cy − ay ) − (by − ay )(cx − ax )
T>0 : 逆时针
T<0 : 顺时针
证明可以使用向量相乘法,或者判定余弦正负的方法。