当前课程知识点：Data Structures and Algorithm Design Part I >  03.List >  E.Insertionsort >  03E-6

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

03E-6在线视频

下一节:03E-7

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

03E-6课程教案、知识点、字幕

那么以上insertion sort算法的性能如何呢？

我们来对此做一分析

首先来看一种最好的情况

这里我们已经把场景给设计好了

也就是说 如果比作是抓牌的过程的话

那么所有的牌都是按照完全

或者至少是几乎有序的次序抵达的

因此 你的理牌过程大概是这样的

最开始 来的是一张最小的牌

接下来的第二张牌呢

至少不会比它更小

第三张也是如此 第四张、第五张

以及后边若干张 也几乎都是这样

为什么说这是最好的情况呢？

因为每当有一张新牌到达

我们向前搜索的过程

只需做一次比较

即可确定应该将这张新的牌

插入于当前的最后位置

一次比较 零次交换

每张牌所需要的时间都是一个单位

累计而言 当然也就是线性了

看好了 线性

为什么需要大家看好呢？

因为我们要和此前所讲的

selection sort 做对比

大家应该还记得

那个算法的复杂度是n平方

而且是θ(n平方) 它的意思是说

没有最好情况 当然也没有最坏情况

在所有的情况下

它都需要n的平方这么多时间

这又是插入排序和选择排序的一大区别

当然相应地 也有最坏的情况

不难设想 这种场景就是

所有的牌完全按照颠倒的次序

也就是逆序来给出

所以即便在任何时候

你已经将手里的牌从小到大

排列成了一个有序的部分

却保不齐下面来的一张牌

会比此前的所有的牌都更小

以致于你必须逐个经过比对之后

才能够确定应该将它插入在最前方的位置

这样为了插入每一张牌

我们所需要经过的搜索

都需要走过漫漫的一条长路

它的长度就是当前你迭代的次数所界定的

每个元素都需要这样

整体构成一个算术级数

我们讲过 它的总和应该又回到了n的平方

这里有一个插曲

有的同学可能会敏锐地注意到

噢 你这里为什么要这样

亦步亦趋地进行查找呢？

你没有注意到吗？

这个地方已经是有序了的

在一个有序的序列中进行查找

你为什么不采用

我们此前所说的二分查找呢？

那么我的回答是

噢 那对不起 如果是那样的话

那我们就不能用列表了

你或许会说

那我们就用Vector呗

啊 事实上也只有Vector

能够支持这种call-by-rank的方式了

嗯 没错

但是我说 这依然存在问题

你如果想深入思考

不妨在这暂停一下

一、二、三

是的 我想聪明的你

已经发现了问题所在

的确 如果我们改用向量

来组织整个序列

包括这个有序的序列

固然可以将这样一个查找的过程加快

具体来说 只需logn的时间

或者说logn次比较

就可以确定一个位置

即便在最坏的情况下

我们可以将原来的线性次比较

减少为logn次

但是很遗憾

在此后

我们为了将新的这个元素

真正地从物理上插入于这样的一个序列

注意 这个时候已经是一个向量

我们不得不将它所有的后继

也就是原来整个这个序列

整体地向后移动一个单位

这意味着什么呢？

这意味着我们的交换操作次数

将变成O(n)

也就是说 原来只需一次交换

现在却需要进行O(n)次

采用列表结构

此前两项累计是O(n)

以致整体是O(n平方)

而现在呢 采用新方案

虽然比较的次数能够降至logn

但是总体所花的时间却依然是n

所以就最坏情况而言

改用向量结构

对于这种算法的改进 于事无补

Data Structures and Algorithm Design Part I课程列表：

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--（a）计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-（xd）：LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

03E-6笔记与讨论

也许你还感兴趣的课程:


  1. 教你学创意(2021秋)

  2. 中医护理技术(2021秋)

  3. Heat Transfer(Round 2)

  4. Roller Skating Course For Beginners(Round 2)

  5. 中国国情与文化概况(2021秋)

  6. 数字逻辑(2021秋)

  7. 工程图学(基础篇)(2021秋)

  8. 岩石物理学(2021秋)

  9. Calculus I(Round 2)

  10. Appreciation of Chinese and Western Cultures(Round 1)

  11. Data Structures and Algorithm Design Part I(Self-Paced)

  12. 清华大学计算机科学与技术系六十周年系庆学术报告（四）大数据(自主模式)

  13. Mechanical Manufacturing Technology(Round 1)

  14. Surgery(Spring 2021)

  15. 临床研究方法学导论(2021春)

  16. 2019年研究生学术与职业素养讲座(自主模式)

  17. 工业互联网大讲堂(自主模式)

  18. Chinese History From Warring States to the Tang Dynasty(Self-Paced)

  19. History of Chinese Architecture Part I(Self-Paced)

  20. Database Technology and Programming(Round 1)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。