August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
58
｜
第
4
章
4.2 移位排序
早期的排序算法是在集合
A
中寻找乱序元素，所用的方法是通过将其与
A
中的其他元素
移位（或交换）来移动到正确的位置。
选择排序
和（名声不太好的）
冒泡排序
都属于此
类排序算法。不过比起插入排序，这类算法的性能依然略逊一筹。下面就让我们了解一
下什么是
插入排序
。
4.2.1 插入排序
插入排序
反复调用
insert
辅助函数来确保
A
[0,
i
]
是有序的
，当
i
最终到达最右边的元素
时，整个
A
集合排序完毕。
插入排序算法小结
最
好情况：
O
(
n
)
平均情况和最坏情况：
O
(
n
2
)
sort (A)
for pos = 1 to n-1 do
insert (A, pos, A[pos])
end
insert (A, pos, value)
i = pos - 1
while i >= 0 and A[i] > value do
❶
A[i+1] = A[i]
i = i-1
A[i+1] = value
❷
end
❶
将大于
value
的元素向右移动。
❷
将
value
插入合适的位置。
图
4-3
显示了
插入排序
是如何运行在一个无序的数据集
A
上的，其中
A
的大小
n
为
16
。
接下来的
15
行描述了每一次调用
insert
后
A
的状态。
算法通过不断将
A
[
pos
]
（
pos
的范围为
1~
n
－
1
）插入有序区域
A
[0,
pos
]
中（这个区域用
粗体竖线隔开）的正确位置，来最终完成对集合
A
的排序。灰色的元素会被移到右边来
为即将插入的元素空出位置。计算下来，
插入排序
总共执行了
60
次的相邻移位（即只
将元素移动 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.