插入排序的算法原理相对来说还是比价容易理解的，也是算法导论里作为基础算法在介绍章节作为铺垫使用，在分析完循环不变性之后，借助插入排序做了循环不变性的证明。
从第二个元素开始选取，不断的用这个元素和以前的进行比较，在第一次比较时，只有第一个元素和第二个元素进行比较，然后依次递增选取的比较元素，需要注意在这个过程中，选取元素之前的队列，都是已经完成了排序的，所以在之前的队列中，一旦发现有违反队列性质的元素，则不断向后移动元素，完成这个过程之后，再将元素写入已经腾出的位置，一直到队列的尾部。
源码如下：
#include <stdio.h>
#include <stdlib.h>
void InsertSort(int* a, int len)
{
for(int j=1; j<len; j++)
{
int key = a[j];
int i = j-1;
while(i>=0 && a[i]>key)
{
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
}
void Print(int* a, int len)
{
for(int i=0; i<len; i++)
{
printf("%d\n", a[i]);
}
}
int main()
{
int x[] = {5,4,3,2,1};
InsertSort(x, 5);
Print(x, 5);
return 0;
}
需要留心在插入 排序的过程中，内部过程使用了while中的与判断，这个前提是在插入之前的队列已经是排序好的，然后在遇到违背队列规则的情况下，就需要开始将要插入的位置移动，但是一旦遇到符合队列规则的条件，while的判断为false，就跳出循环。这比单纯的写个for循环，然后不断地执行if判断，能减少不用再检测的部分。
借着这个机会，查看下该程序对应的汇编代码，对CPU的运行再回顾下
编译指令 ：
gcc -g -c tes.cpp
objdump -S tes.o -o tes.S
tes01.o： 文件格式 elf64-x86-64
Disassembly of section .text:
0000000000000000 <_Z10InsertSortPii>:
#include <stdio.h>
#include <stdlib.h>
void InsertSort(int* a, int len)
{
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 48 89 7d e8 mov %rdi,-0x18(%rbp)
8: 89 75 e4 mov %esi,-0x1c(%rbp)
for(int j=1; j<len; j++)
b: c7 45 fc 01 00 00 00 movl $0x1,-0x4(%rbp)
12: e9 9a 00 00 00 jmpq b1 <_Z10InsertSortPii+0xb1>
{
int key = a[j];
17: 8b 45 fc mov -0x4(%rbp),%eax
1a: 48 98 cltq
1c: 48 8d 14 85 00 00 00 lea 0x0(,%rax,4),%rdx
23: 00
24: 48 8b 45 e8 mov -0x18(%rbp),%rax
28: 48 01 d0 add %rdx,%rax
2b: 8b 00 mov (%rax),%eax
2d: 89 45 f4 mov %eax,-0xc(%rbp)
int i = j-1;
30: 8b 45 fc mov -0x4(%rbp),%eax
33: 83 e8 01 sub $0x1,%eax
36: 89 45 f8 mov %eax,-0x8(%rbp)
while(i>=0 && a[i]>key)
39: eb 34 jmp 6f <_Z10InsertSortPii+0x6f>
{
a[i+1] = a[i];
3b: 8b 45 f8 mov -0x8(%rbp),%eax
3e: 48 98 cltq
40: 48 83 c0 01 add $0x1,%rax
44: 48 8d 14 85 00 00 00 lea 0x0(,%rax,4),%rdx
4b: 00
4c: 48 8b 45 e8 mov -0x18(%rbp),%rax
50: 48 01 c2 add %rax,%rdx
53: 8b 45 f8 mov -0x8(%rbp),%eax
56: 48 98 cltq
58: 48 8d 0c 85 00 00 00 lea 0x0(,%rax,4),%rcx
5f: 00
60: 48 8b 45 e8 mov -0x18(%rbp),%rax
64: 48 01 c8 add %rcx,%rax
67: 8b 00 mov (%rax),%eax
69: 89 02 mov %eax,(%rdx)
i--;
6b: 83 6d f8 01 subl $0x1,-0x8(%rbp)
{
for(int j=1; j<len; j++)
{
int key = a[j];
int i = j-1;
while(i>=0 && a[i]>key)
6f: 83 7d f8 00 cmpl $0x0,-0x8(%rbp)
73: 78 1b js 90 <_Z10InsertSortPii+0x90>
75: 8b 45 f8 mov -0x8(%rbp),%eax
78: 48 98 cltq
7a: 48 8d 14 85 00 00 00 lea 0x0(,%rax,4),%rdx
81: 00
82: 48 8b 45 e8 mov -0x18(%rbp),%rax
86: 48 01 d0 add %rdx,%rax
89: 8b 00 mov (%rax),%eax
8b: 3b 45 f4 cmp -0xc(%rbp),%eax
8e: 7f ab jg 3b <_Z10InsertSortPii+0x3b>
{
a[i+1] = a[i];
i--;
}
a[i+1] = key;
90: 8b 45 f8 mov -0x8(%rbp),%eax
93: 48 98 cltq
95: 48 83 c0 01 add $0x1,%rax
99: 48 8d 14 85 00 00 00 lea 0x0(,%rax,4),%rdx
a0: 00
a1: 48 8b 45 e8 mov -0x18(%rbp),%rax
a5: 48 01 c2 add %rax,%rdx
a8: 8b 45 f4 mov -0xc(%rbp),%eax
ab: 89 02 mov %eax,(%rdx)
#include <stdio.h>
#include <stdlib.h>
void InsertSort(int* a, int len)
{
for(int j=1; j<len; j++)
ad: 83 45 fc 01 addl $0x1,-0x4(%rbp)
b1: 8b 45 fc mov -0x4(%rbp),%eax
b4: 3b 45 e4 cmp -0x1c(%rbp),%eax
b7: 0f 8c 5a ff ff ff jl 17 <_Z10InsertSortPii+0x17>
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
}
bd: 5d pop %rbp
be: c3 retq
00000000000000bf <_Z5PrintPii>:
void Print(int* a, int len)
{
bf: 55 push %rbp
c0: 48 89 e5 mov %rsp,%rbp
c3: 48 83 ec 20 sub $0x20,%rsp
c7: 48 89 7d e8 mov %rdi,-0x18(%rbp)
cb: 89 75 e4 mov %esi,-0x1c(%rbp)
for(int i=0; i<len; i++)
ce: c7 45 fc 00 00 00 00 movl $0x0,-0x4(%rbp)
d5: eb 2b jmp 102 <_Z5PrintPii+0x43>
{
printf("%d\n", a[i]);
d7: 8b 45 fc mov -0x4(%rbp),%eax
da: 48 98 cltq
dc: 48 8d 14 85 00 00 00 lea 0x0(,%rax,4),%rdx
e3: 00
e4: 48 8b 45 e8 mov -0x18(%rbp),%rax
e8: 48 01 d0 add %rdx,%rax
eb: 8b 00 mov (%rax),%eax
ed: 89 c6 mov %eax,%esi
ef: bf 00 00 00 00 mov $0x0,%edi
f4: b8 00 00 00 00 mov $0x0,%eax
f9: e8 00 00 00 00 callq fe <_Z5PrintPii+0x3f>
}
}
void Print(int* a, int len)
{
for(int i=0; i<len; i++)
fe: 83 45 fc 01 addl $0x1,-0x4(%rbp)
102: 8b 45 fc mov -0x4(%rbp),%eax
105: 3b 45 e4 cmp -0x1c(%rbp),%eax
108: 7c cd jl d7 <_Z5PrintPii+0x18>
{
printf("%d\n", a[i]);
}
}
10a: c9 leaveq
10b: c3 retq
000000000000010c <main>:
int main()
{
10c: 55 push %rbp
10d: 48 89 e5 mov %rsp,%rbp
110: 48 83 ec 20 sub $0x20,%rsp
int x[] = {5,4,3,2,1};
114: c7 45 e0 05 00 00 00 movl $0x5,-0x20(%rbp)
11b: c7 45 e4 04 00 00 00 movl $0x4,-0x1c(%rbp)
122: c7 45 e8 03 00 00 00 movl $0x3,-0x18(%rbp)
129: c7 45 ec 02 00 00 00 movl $0x2,-0x14(%rbp)
130: c7 45 f0 01 00 00 00 movl $0x1,-0x10(%rbp)
InsertSort(x, 5);
137: 48 8d 45 e0 lea -0x20(%rbp),%rax
13b: be 05 00 00 00 mov $0x5,%esi
140: 48 89 c7 mov %rax,%rdi
143: e8 00 00 00 00 callq 148 <main+0x3c>
Print(x, 5);
148: 48 8d 45 e0 lea -0x20(%rbp),%rax
14c: be 05 00 00 00 mov $0x5,%esi
151: 48 89 c7 mov %rax,%rdi
154: e8 00 00 00 00 callq 159 <main+0x4d>
return 0;
159: b8 00 00 00 00 mov $0x0,%eax
}
15e: c9 leaveq
15f: c3 retq
按照程序的内存分配方式，可以分为 代码段， 数据段，堆栈段， 代码段是只读的， 数据段存放的全局变量以及static变量，在程序的整个生命周期都是存在的；堆栈段的内存是动态开辟的。
这其中有些细节需要注意下，
代码段虽然名为代码段，但是里面存储的都是程序中只读的部分，例如执行代码，以及像"abcdef"这种存放在常量区的字符串，用c++的const关键字限定为不可修改的也存放在该区。
数据段虽然存放的是全局变量以及static静态变量，但是对于 已经赋值的全局变量，存放在.data区，已经分配了内存空间；未赋值的全局变量，存放在.bss区，只是做了符号生命，在程序执行期开辟内存，所以未初始化全局变量的程序将比已经赋值全局变量的程序更庞大。这就是为什么数据区要分为 .data区和.bss区的原因。
堆栈区是堆区和栈区的统称，这里的堆栈与数据结构中的堆栈是两个概念，不要混淆。 堆区的开辟和释放由程序负责，具体表现就是由new和malloc/cmalloc进行开辟，由delete/delete[]和free进行释放，开辟的大小，由程序制定，具体查看man手册中对于malloc和cmalloc的用法， 使用c++的new开辟类的内存与类的大小 有关。
栈区由cpu管理，分配的大小有限制，例如int,double,float,short等等这些类型，其实就是指定分配的内存空间字节大小，已经被限定，cpu寄存器的ss段寄存器存放了栈区 的段地址， sp寄存器一直 指向了栈区的栈顶，是在不断变化的，在进入函数时，函数的局部变量存放在栈区，在函数执行过程中，sp指针不断变化。在调用函数过程中，这个过程需要另外的ep寄存器，专门用来记录此时的ep寄存器的值，目的在sp指针变化时，仍然能够压栈进入的函数参数。
可以细心留一下ep和sp的变化。
