简介/直接插入排序
基本思想待排序记录 R1，R2，… ，Rn–1, Rn第一步：R1第二步：(R1 ), R2第三步：(R1 , R2), R3……第 j 步：(R1，R2，… ，Rj–1), Rj……第 n 步: (R1，R2，… ，Rn–1), Rn．例：j=5原有序表中关键词比Rj大的记录数：dj比较次数：dj+1 移动次数： dj+2算法思想算法 InsertSort (R,n)FOR j=2 TO n DO( //每次将Rj插入到有序表R1，…，Rj–1中K←Kj. R←Rj. i←j-1.WHILE (i>0) AND (Ki>K) DO(Ri+1←Ri.i←i-1.)Ri+1←R.)算法InsertSortA( R, s, e )//引入虚拟记录,Ks-1≤min{Ki| s≤i≤e}ISA1 [逐一排序]FOR j=s+1 TO e DO( i←j-1．K←Kj. R←Rj .WHILE K( Ri+1←Ri ．i←i-1 ．)Ri+1←R ．)ISA1 [逐一排序]FOR j=s+1 TO e DO( i←j-1．K←Kj . R←Rj .WHILE K( Ri+1←Ri ．i←i-l ) ．Ri+1←R )直接插入排序的时间复杂度为 O(n2)。排序方法1．简单方法首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1)；然后将R[k．．i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。注意：若R[i]的关键字大于等于R[1．．i-1]中所有记录的关键字，则R[i]就是插入原位置。2．改进的方法一种查找比较操作和记录移动操作交替地进行的方法。具体做法：将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较：① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。
作法/直接插入排序
直接插入排序(straight insertion sort)的作法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止
哨兵的作用/直接插入排序
算法中引进的附加记录R称监视哨或哨兵(Sentinel)。哨兵有两个作用：①进人查找(插入位置)循环之前，它保存了R[i]的副本，使不致于因记录后移而丢失R[i]的内容；②它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R.key和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。注意：①实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。【例】单链表中的头结点实际上是一个哨兵②引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。
过程实例/直接插入排序
例：原有序表：(9 15 23 28 37) 20找插入位置 : (9 15 ^ 23 28 37) 20新有序表: (9 15 20 23 28 37)设待排序的文件有8个记录，其关键字分别为：49，38，65，97，76，13，27，49。为了区别两个相同的关键字49，后一个49的下方加了一下划线以示区别。其排序过程见
序列/直接插入排序
初始序列i=1 58 15 45 90 18 10 62↓i=2 &#91;46 58&#93; 15 45 90 18 10 62┌——┘↓i=3 &#91;15 46 58&#93; 45 90 18 10 62┌——┘↓i=4 &#91;15 45 46 58&#93; 90 18 10 62↓i=5 &#91;15 45 46 58 90&#93; 18 10 62┌—————┘↓i=6 &#91;15 18 45 46 58 90&#93; 10 62┌————————┘↓i=7 &#91;10 15 18 45 46 58 90&#93; 62┌—┘↓i=8 &#91;10 15 18 45 46 58 62 90&#93;C/C++代码实现直接插入排序void insert_sort(int a&#91;&#93;, int n){int i, j,for (i = 1; i < ++i){temp = a&#91;i&#93;;for (j = j>0 && temp < a&#91;j - 1&#93;; --j){a&#91;j&#93; = a&#91;j - 1&#93;;}a&#91;j&#93; =}}java代码实现直接插入排序public class MainTest {public static void main(String&#91;&#93; args) {int&#91;&#93; a = { 46, 58, 15, 45, 90, 18, 10, 62 };int n = a.int i,for (i = 0; i < i++) {int temp = a&#91;i&#93;;for (j = j > 0 && temp < a&#91;j-1&#93;; j--) {a&#91;j&#93; = a&#91;j - 1&#93;;}a&#91;j&#93; =}for(i=0;iSystem.out.print(a&#91;i&#93;+"\t");}}}Objective-C实现?71819+(void)sort:(NSMutableArray*)array{inti,y;for(i=0;i<[arraycount]-1;i++){//前面一位大于后面一位if([[arrayobjectAtIndex:i+1]intValue]0&&[[arrayobjectAtIndex:y-1]intValue]>[tempintValue];y--){[arrayexchangeObjectAtIndex:y-1withObjectAtIndex:y];}//[arrayremoveObjectAtIndex:y];//[arrayinsertObject:tempatIndex:y];}}}C#实现?publicvoidAction(int[]array){for(inti=1;i=0&&tem<array[j];j--){array[j+1]=array[j];}array[j+1]=}}}
&|&相关影像
互动百科的词条（含所附图片）系由网友上传，如果涉嫌侵权，请与客服联系，我们将按照法律之相关规定及时进行处理。未经许可，禁止商业网站等复制、抓取本站内容；合理使用者，请注明来源于。
登录后使用互动百科的服务，将会得到个性化的提示和帮助，还有机会和专业认证智愿者沟通。
此词条还可添加&
编辑次数：12次
参与编辑人数：10位
最近更新时间： 23:28:27
认领可获得以下专属权利：
贡献光荣榜用有序列插入排序法把38插入到有序列10.13.18.26.37.39.46.70中.共需要比较的次数为A．4 B．5 C．6 D．4或6 题目和参考答案——精英家教网——
成绩波动大？难提高？听顶级名师视频辅导，
& 题目详情
用有序列插入排序法把38插入到有序列10，13，18，26，37，39，46，70中，共需要比较的次数为（&&& ）A．4&& &&&&&&&&&&&&&B．5&&& &&&&&&&&&&&C．6&& &&&&&&&&&&&&&D．4或6
解析：按照有序列插入排序法的思想和操作步骤，应将38逐一与已有的序列的各个数字作比较，直到找到38所在的位置.操作过程如下：&&& 从左向右依次比较，首先38与10比较，由于38＞10,继续与下一个比较,由于38＞13,所以,继续将38与后一个数18比较,由于38＞18,故继续,直到找到38的位置，这样共需比较6次.同理若从右向左依次比较则需比较4次.答案：D温馨提示&&& 用有序列插入排序法对一有序列进行排序时，关键的问题是要确定插入的数在原数列中的位置，在应在的位置时，它必须满足大于前一个数，且小于后一个数.
请在这里输入关键词：
科目：高中数学
来源：学习周报　数学　北师大课标高一版(必修3)　学年　第31期　总187期 北师大课标版
用有序列直接插入排序法把23插入有序列{5，8，11，24，33，45，48，50}中，则23在该有序列中的序号为________．
科目：高中数学
来源：数学教研室
把由m个数据组成的无序列用直接插入排序法排成有序列，最多可经过(　　)次有序列插入排序过程就可完成
A．mB．m－1C．m＋1D．2m
科目：高中数学
把由m个数据组成的无序列用直接插入排序法排成有序列，最多可经过(　　)次有序列插入排序过程就可完成
科目：高中数学
题型：单选题
把由m个数据组成的无序列用直接插入排序法排成有序列，最多可经过次有序列插入排序过程就可完成A.mB.m-1C.m+1D.2m
精英家教网新版app上线啦！用app只需扫描书本条形码就能找到作业，家长给孩子检查作业更省心，同学们作业对答案更方便，扫描上方二维码立刻安装！
请输入姓名
请输入手机号19318人阅读
算法集中营（19）
数据结构（26）
C/C++语言（60）
声明：引用请注明出处
在我的博文《》中给出的首个算法就是高效的排序算法。本文将对排序算法做一个全面的梳理，从最简单的“冒泡”到高效的堆排序等。
排序相关的的基本概念
排序：将一组杂乱无章的数据按一定的规律顺次排列起来。
数据表( data list): 它是待排序数据对象的有限集合。
排序码(key):通常数据对象有多个属性域，即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。
内排序：指在排序期间数据对象全部存放在内存的排序；
外排序：指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
排序算法的分析
排序算法的稳定性
如果在对象序列中有两个对象r[i]和r[j] ,它们的排序码k[i]==k[j] 。如果排序前后,对象r[i]和r[j] 的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。
排序算法的评价
排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。
算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算
算法执行时所需的附加存储。
插入排序(Insert Sorting)
每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。
根据寻找插入位置方法分为
直接插入排序
折半（二分）插入排序
希尔插入排序
直接插入排序
当插入第i(i≥1)个对象时,前面的V[0],V[1],…,V[i-1]已经排好序。这时,用V[i]的排序码与V[i-1],V[i-2],…,V[0]的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的对象向后顺移。
直接插入排序图示
从上到下，分别展示了直接排序算法的所有可能的过程，包括相同排序码的排序方式（保持了原来的顺序，说明是稳定排序）以及in-place操作中的元素移动等。
直接插入排序算法分析
设待排序对象个数为n,则该算法的主程序执行n-1趟排序码比较次数和对象移动次数与对象排序码的初始排列有关。
最好情况下,排序前对象已经按照要求的有序。比较次数(KCN):n-1 ;
移动次数(RMN):为0。则对应的时间复杂度为O(n)。
最坏情况下,排序前对象为要求的顺序的反序。第i趟时第i个对象必须与前面i个对象都做排序码比较,并且每做1次比较就要做1次数据移动（具体可以从下面给出的代码中看出）。比较次数(KCN):∑n-1i=1i=n(n-1)2≈n22 ;
移动次数(RMN):为∑n-1i=1i=n(n-1)2≈n22。则对应的时间复杂度为O(n2)。
如果排序记录是随机的，那么根据概率相同的原则，在平均情况下的排序码比较次数和对象移动次数约为n24，因此，直接插入排序的时间复杂度为O(n2)。
直接插入排序算法的特点
它是稳定排序，不改变相同元素原来的顺序。
它是in-place排序，只需要O(1)的额外内存空间。
它是在线排序，可以边接收数据边排序。
它跟我们牌扑克牌的方式相似。
对小数据集是有效的。
To save memory, most implementations use an in-place sort that works by moving the current item past the already sorted items and repeatedly swapping it with the preceding item until it is in place.
直接排序的代码（C++版本）
伪代码如下：
for i = 1, n
while(j & 0 and E[j] & E[j-1])
swap(E[j], E[j-1])
#include &iostream&
#include &iomanip&
using namespace std;
void swap(int &x, int &y)
int temp =
void insertion(int a[], int sz)
for(int i=1; i
while(j & 0 && (a[j] & a[j-1])) {
swap(a[j], a[j-1]);
for (int k = 0; k & k++) cout && setw(3) && a[k];
int main()
int a[] = { 15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14};
int size = sizeof(a)/sizeof(int);
for (int i = 0; i & i++) cout && setw(3) && a[i];
insertion(a, size);
过程输出：
9 11 15 12 13
9 11 12 15 13
9 11 12 13 15
9 11 12 13 15
9 11 12 13 15
9 11 12 13 15 16
9 11 12 13 15 16
9 11 12 13 15 16 10 14
9 10 11 12 13 15 16 14
9 10 11 12 13 14 15 16
下面是使用链表的直接插入排序算法：
#include &iostream&
using namespace std;
struct List
struct List *
void printList(struct List *head)
struct List* ptr =
while(ptr) {
cout && ptr-&data && " " ;
ptr = ptr-&
struct List* createList(int a[], int sz)
struct List *head = new struct L
struct List *current =
for(int i = 0; i & i++) {
current-&data = a[i];
if (i == sz - 1 ) {
current-&next = NULL;
current-&next = new struct L
current = current-&
struct List* insertion(struct List *head)
if(head == 0) return
struct List *unsorted = head-&
while(unsorted != 0)
struct List *prev = 0;
struct List *iter =
struct List *key =
while(iter != 0)
if(iter-&data & key-&data)
iter = iter-&
unsorted = unsorted-&
if(iter == key)
struct List *replace =
while(iter-&next != key) iter=iter-&
iter-&next =
if(prev == 0) {
prev-&next =
key-&next =
printList(head);
int main()
int a[] = { 15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14};
int size = sizeof(a)/sizeof(int);
struct List *head = createList(a, size);
printList(head);
head = insertion(head);
printList(head);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：749170次
积分：11379
积分：11379
排名：第1161名
原创：263篇
转载：777篇
评论：127条
文章：18篇
阅读：21852
文章：50篇
阅读：97290
文章：24篇
阅读：59065
文章：47篇
阅读：75206