算法不会，尚能饭否之排序——直接插入排序（Insert sort）

迈不过友情╰ 2023-08-17 15:50 42阅读 0赞

这是春节过后写的第一篇博文，大家都有一样的感觉，春节过后，人都有点不想动了，说实话，我也

不想写的！没有办法。借着晚上的酒劲，就写了这篇直接排序(Insert Sort)的博文。

现在转移战场了，现在开始进军排序这块算法之地了。而本节将重点讲解直接插入排序。现在大家就

听本人娓娓道来！有钱的捧个钱场，没钱的捧个人场！

众所周知！排序，在以后的编程生涯中的地位是多么的重要的，地位的重要性，鄙人就不在此浪费口

舌了。重点还是放在算法的思想精髓上来。

在前面的博文中，我也讲了一般的数据结构有数组、链表、树和图！而直接插入排序可以用数组和链

表都可以实现。而链表实现在我的以前博文中有讲，但是题目不是《算法不会，上能饭否》这个系列的，

但是在数据结构这个目录下可以找到。所以，我这里主要还是讲用数组实现直接插入排序(Insert Sort)！

算法思想：当插入第i（i>= 1）个对象时，前面的v\[0\], v\[1\], v\[2\],……v\[i - 1\]都已经排列好了，而你现在需

要做的就是，将v\[i\]的值与v\[i - 1\], v\[I - 2\]……的值顺序进行比较，找到插入位置就将v\[i\]插入，原来位置上的

对象向后顺序移动。

算法思想总的讲起来很是简单。区区几行字，没有什么大不了的，没有什么递归，回溯等等需要你去

动脑经的，就是一个找到一个合适的位置，讲数组中的在合适位置之后的之向后顺序移动（前提是你会这

么做，很熟悉懂得数组元素的插入，再这里就不用了解删除了，如果你还稍微欠了点火候，再我的这个目

录下有一篇博文，是关于顺序表的，主要讲的就是数组的一些基本操作，不妨去看看！），然后就是想当

然的插入了。So easy!

再这个过程中的如何一步步的走这个算法，我就不画图了，画图却是很费时间的。现在还是主要看代

码!

注：本程序在visual studio 2008下编译通过，如果编译不能通过，请选择visual studio 2008.

再注：上一个注非广告，请大家见谅！同时，本人的博客关于C++的博文中涉及的代码都在visual studio

2008中经本人亲自测试通过，如有问题，请留言提出。谢谢！

再注：如转载本博文，请注明出处，谢谢合作！因为写博文也是一件不容易的事情，请尊重我的劳动成

果！

代码如下：

\#include <iostream> \#include <stdlib.h> using namespace std; void InsertSort(); //插入排序函数 int main() \{ InsertSort(); \} void InsertSort() \{ int num; //排序的数的个数 cout<<"请输入排序个数:"; cin>>num; //判断输入错误，退出程序 if (num <= 0) \{ cout<<"输入错误!"<<endl; exit(0); \} int \*Array = new int\[num\]; //动态开辟存放参加排序的数的数组 for (int i = 0; i < num; i++) \{ cin>>Array\[i\]; if (i == 0) \{ continue; //第一个数，直接放入数组，不用排序 \} //进行排序循环 for (int j = 0; j < i; j++) \{ if (Array\[i\] > Array\[j\]) \{ continue; \} else \{ int temp = Array\[i\]; //记录Array\[i\]，防止被覆盖 //向后移动，将小的插入，数组的移动操作 for (int m = i; m >= j; m--) \{ Array\[m\] = Array\[m - 1\]; \} Array\[j\] = temp; \} \} \} //输出排序结果 cout<<"排序结果输出:"; for (int n = 0; n < num; n++) \{ cout<<Array\[n\]<<","; \} cout<<"/n"; delete\[\] Array; //删除动态数组开辟的空间 \}

好了，博文写到此出为止！如有问题，或者对这个程序还是觉得有什么不满意，请留言提出！你我共同进

步！谢谢！

转载于:https://www.cnblogs.com/JPAORM/archive/2011/03/20/2509900.html