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

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

03E-8在线视频

下一节:03XD

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

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

在结束这一节之前

我们再来讨论与插入排序非常相关

也是非常有意思的一个问题

我们来介绍这么样一个概念

也就是逆序对 inversion

对于任何一个序列

我们都可以在其中发现这种逆序对

既然是对 肯定就涉及到两个元素

没错

如果有某两个元素一左一右

而且左侧更大一些 右侧更小一些

我们就称它们构成了一个逆序对 一个inversion

当然反过来 如果是这样的顺序的

也就是左小右大的形式

这就不是个逆序对

当然你也可以称它叫作顺序对

实际上 在整体的n个元素中

任何两个元素都可能构成一个逆序对

因此 对于一个长度为n的序列而言

逆序对的总数有可能会多达n平方

那么inversion和我们这一节的主题

insertion sort是什么关系呢?

为了说明方便

我们先还要做一个铺垫的工作

我们看到inversion实际上

涉及到的是两个元素

这样不利于我们记帐

我们不妨采用一个统一的习惯 也就是

将每一个inversion都记入到后边

也就是靠右的那个元素的帐上去

因此我们只需要

在这种意义下 统计每一个元素

所对应的inversion有多少个

那么累计而言 就得到了

整个序列中所蕴含的逆序对的数目

再强调一遍 我们将每一个逆序对

都记到后者的帐上去

于是对于任何的一个节点p

我们都可以依此来定义

它所对应的逆序对的数目 记作i(p)

所有节点p所对应逆序对数的总和

也就是 整个序列所包含逆序对的总数

好了

回到插入排序的一般的场景

也就是说 如果当前有序的前缀为s

我们就要将无序后缀中的首元素

插入到这个前缀中的适当位置

正像我们此前所讲过的

这个对应的位置是一个切分点

在它之前 都是比待插入元素e

不大的元素

而反过来呢

在这个分界点之后的那些元素

都应该严格大于这个待插入的元素e

左边都不大于e 而右边都大于e

这说明什么呢?

这说明这个区间内的任何一个元素

都与待插入元素e构成了一个inversion

而且这个inversion正好能归入到

刚才我们记帐于p的那样一个统计值中

或者反过来讲

p所对应的inversion有多少个

p就需要经过多少次比较

才能抵达最终的插入位置

从这个意义上说

i(p)其实就是p所对应的查找长度

因此 如果我们将整个序列中

所包含的逆序对数 记作大I

那么这个大写的I

实际上 也就对应于插入排序算法

在一次又一次定位搜索过程中

比较次数的累计总和

而这个我们说过

就是这个算法所消耗时间的最主要部分

当然不要忘了还有另一部分

也就是对元素真正实施

插入操作所花费的时间

每个元素各自是1 累计是n

所以确切地讲

插入排序所需要的时间

应该是这两个量的总和

而刚才我们所分析的

最好情况和最坏情况呢

无非是它的特例

在最好情况下

我们讲过 它的复杂度是n

为什么是n呢?

回忆一下 最好情况

就是所有的元素都是顺序输入的

逐次递增

我们可以看到 在这样的一个序列中

根本就不含任何的逆序对

逆序对的总数是0

那么0加上n 当然也就是n了

反过来 再看最坏的情况

也就是 完全逆序输入的情况

这个时候我们说过

它的复杂度是n平方

为什么是n平方呢?

因为对于这样一种输入序列而言

其中任何一对元素都是逆序的

因此 它的逆序对的总数

当然也就等于

所有n个元素两两组合的总数

这个总数恰好就是n平方量级的

概括一下 从逆序对的角度来看

可以将插入排序算法的复杂度

度量为这样的一个结果

而这个结果向下可以很好的解释

并且对应于最好的情况

向上也可以很好的解释

并对应于最坏的情况

它是一个更一般的表示

也是一个更加本质的解释

就这样的意义而言

我们如果把刚才的逆序对总数

也就是I 作为序列无序程度的度量尺度

那么insertion sort

就可以理解为是

通过一次一次的努力

去修复这种无序性

原来有多无序 它就需要多少次修复

因此它的算法复杂度

其实不光是取决于问题的规模

而更多的是取决于

输入本身所具有的特性

也就是它的无序程度

所以这样一种算法

也称作输入敏感的

input-sensitive

在排序算法家族中

并非每一种算法都具有这样的一个特性

而插入排序 也正因为它具有这样一个特性

而显得非常的独特

在我们最终要介绍的希尔排序中

我们将会看到

这种特性对于希尔排序整体的性能

乃至这个算法的有效性

都是至关重要的

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-8笔记与讨论

也许你还感兴趣的课程:

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