插入排序
本页面将简要介绍插入排序。
简介¶
插入排序(英语:Insertion sort)是一种简单直观的排序算法。它的工作原理为将待排列元素划分为“已排序”和“未排序”两部分,每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。
一个与插入排序相同的操作是打扑克牌时,从牌桌上抓一张牌,按牌面大小插到手牌后,再抓下一张牌。
性质¶
稳定性¶
插入排序是一种稳定的排序算法。
时间复杂度¶
插入排序的最优时间复杂度为 O(n),在数列几乎有序时效率很高。
插入排序的最坏时间复杂度和平均时间复杂度都为 O(n^2)。
代码实现¶
伪代码¶
\begin{array}{ll}
1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\
2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order stably.} \\
3 & \textbf{Method. } \\
4 & \textbf{for } i\gets 2\textbf{ to }n\\
5 & \qquad key\gets A[i]\\
6 & \qquad j\gets i-1\\
7 & \qquad\textbf{while }j>0\textbf{ and }A[j]>key\\
8 & \qquad\qquad A[j + 1]\gets A[j]\\
9 & \qquad\qquad j\gets j - 1\\
10 & \qquad A[j + 1]\gets key
\end{array}
C++¶
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Python¶
1 2 3 4 5 6 7 8 9 |
|
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用