TsingHuaDSA-排序

该文章为清华大学数据结构与算法设计MOOC课程读书笔记.

1. 快速排序

1.1 思想

类似于merge sort,都是采用分而治之的思路。但是不同的是:

  1. 在归并排序中主要思考的问题是:给出两个用递归已经sort好的数组,如何合并?(首递归)
  2. 而对于快速排序而言,主要思考的问题在于:如何将给定的一个无序数组划分为两部分,使得这两部分相对来说有大小关系,然后再去递归。(尾递归)

1.2 如何划分(Partition)?

第一个问题:轴点(pivot)的选取

思路1:都取第一个。
思路2:随机洗牌之后取第一个。

思路2更好,因为在概率上更容易得到平衡划分。

第二个问题:如何根据轴点划分

两个指针两头逼近,必要时交换数据。


Partition
1.3 算法性能
  • 不稳定
  • 空间:常数
  • 时间:与pivot的选取有关!
  • 如果pivot的划分都很均衡,使得子问题都被划分为一半因此最好O(nlgn)。
  • 如果pivot的划分都很不均衡,使得子问题的规模只被减少一点,因此最差O(n^2)
  • 平均性能O(NlgN)

2. 排序引出的问题:选取问题

2.1 问题的特点

从一组大小可以相互比较的元素中,找到某一个满足某个条件的特殊元素。比如:

  • 找第k个
  • 找中位数median
  • 找众数majority - 元素的个数超过总数一半
    ...

最naive的想法就是利用sorting,然后再进行选择。但是sort的效率算比较低的,最好也才O(nlgn)。因此需要更高效的方法!

2.2 求众数

思路一:利用中位数求众数
  • 必要性:若存在众数,那它必然是中位数!
  • 思路:求中位数 + 判断中位数是不是众数(遍历 + 统计个数)
  • 问题:需要高效的求中位数方法
思路二:利用频繁数(mode)求中位数
  • 必要性:若存在众数,那它必然是频繁数!
  • 思路:求频繁数 + 判断频繁数是不是众数(遍历 + 统计个数)
  • 问题:也需要高效的求频繁数方法
高效求解众数的思路:减而治之
  • 关键:将求解众数问题规模减小
减而治之求众数

2.2 求第k个元素

思路一:排序
  • 缺点:效率太低
思路二:利用一个极小堆MinHeap,不断取出。
  • 思路:将所有元素建一个极小堆,然后一个一个取出,直到第k个
  • 效率:也不高
min heap
思路三:利用一个极大堆MaxHeap,不断插入和移除。
  • 思路:将k个元素建一个极大堆,然后在剩余的元素中一个先插入,再取出,直到最后一个插入。此时堆顶为全局第k大。
  • 效率:取决于k的大小,也不高
  • 理解:当第n次次插入时,堆顶元素是目前所见的倒数第n大数。因此当第n-k次插入时,堆顶为全局倒数第n - k大数,即顺数第k大。


    max heap
思路四:利用一大一小堆
  • 理解:利用堆顶比较之后的互换,保证在最后,有k - 1个元素不大于大堆顶的元素且有n-k个元素也不小于它。它即为第k大。
  • 效率:worst case也还是不高


    max heap + min heap
思路五:基于减而治之思想的quick-select
  • 思想:利用quick select中的partition将问题规模减小
  • 效率:最好O(n),但是最差也会到O(n^2)
  • 理解:最好每次问题规模可以减少一般(n + n/2 + n/4 + ... = O(n));最坏每次问题规模只减少1(n + n-1 + n-2 + ... = O(n^2))


    quick-select
思路六:基于减而治之思想的linear-select
  • 思想:找中位数中的中位数!
  • 效率:线性!
linear-select

3. 希尔排序

  • 思路:根据步长序列(step sequence),先进行大步长排序,再进行小步长排序,直到步长为1.
  • 采用的基本排序方法:插入排序,因为其输入敏感性,对约有序的序列,效率越高。
  • 步长序列的选择:
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,937评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,503评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,712评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,668评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,677评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,601评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,975评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,637评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,881评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,387评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,971评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2 342

推荐阅读更多精彩内容

  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,727评论 0 15
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,164评论 0 52
  • 刚开学… 小孩上学… 成了热门话题… 第一天上学就掉田里了… 各位… 看到了吧… 水稻田也不是当年的水稻田… 农村...
    计学撮要_阅读 232评论 0 0
  • 今日从马德里到巴塞罗那,住的酒店有点恐怖,还是不大习惯民宿,感觉脏脏的,还阴森森的,巴塞罗那给人的气氛也比马德里要...
    帅气梁朝伟阅读 209评论 0 0
  • 雄创_Jasic阅读 312评论 0 0