普林斯顿算法中级笔记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 ~ N2/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/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...
...


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

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

  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的直线与横坐标之间的夹角的从大到小的顺序排列并命名。


    屏幕快照 2018-08-04 下午12.43.27.png
  • 我们知道以下事实,如果该点是边界上的顶点,那么从起点p,依次连接所有顶点的路径,应该是完全逆时针的。由此我们可以确定处所有的顶点。
  • 从点1 开始,遍历所有的点,依次连接,若路径中出现顺时针,则抛弃到时第二个点。
出现这种情况则抛弃点 3
出现这种情况则抛弃点 2.
  • 如何判定三个点之间的路径是顺时针还是逆时针?
    T=(bx − ax )(cy − ay ) − (by − ay )(cx − ax )
    T>0 : 逆时针
    T<0 : 顺时针
    证明可以使用向量相乘法,或者判定余弦正负的方法。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,607评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,047评论 2 379
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,496评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,405评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,400评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,479评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,883评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,535评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,743评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,544评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,612评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,309评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,881评论 3 306
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,891评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,136评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,783评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,316评论 2 342

推荐阅读更多精彩内容