前言：这算是第一系列的博客，常见算法的实现。水平有限，语言组织能力有限，请观者轻喷。
第一系列。我所熟知的武功路数，七种排序，三种查询。
所有存储结构都是数组，算法的实现语言C++,java.
我会按照如下排版格式写：
一、算法实现思想；
二、关于算法的思考，以及执行步骤的区分；
三、对算法的具体代码实现（JAVA，C++）；
四、时间空间、效率、稳定性分析；
五、实际应用；
--------------------------------------------------------我是正式开始的分割线 ------------------------------------------------------------------------
第一种武功：插入排序
插入排序分为两类，直接插入排序（InsertSort）和希尔排序(ShellSort)。
一、算法实现思想；
InsertSort算法实现思想：
依次将待排序中的每一条记录插入到有序序列中直到所有的记录有序。
ShellSort算法实现思想：
将待排序的记录分为若干子序列，在子序列内进行直接插入排序。待整个序列基本有序再对全体记录进行直接插入排序。
二、关于算法的思考，以及执行步骤的区分；
InsertSort算法实现
如何构造初始有序序列？
以数组的第一个元素作为初始有序序列
如何查找待插入的记录？
从数组的第二个元素开始依次和有序序列进行比较，找到合适的存放位置。有序序列递增，无序序列递减。
ShellSort算法实现
如何构造子序列（完成对子序列的划分）？
为了达到构造的子序列接近基本有序，设置D=N/2模式
如何在子序列中进行直接插入排序？
和直接插入排序一样，在每一次的划分中，对当前小组的数进行直接插入排序。方法类似上面直接插入排序
三、对算法的具体代码实现（JAVA，C++）；
直接插入排序的C++代码实现
/* *直接插入排序的实现 * 前置条件:无顺序的一个数组 * 输 入:数组以及数组长度 * 处 理:对数组完成直接插入排序 * 输 出:有序数组 * 后置条件:无 */ void InsertSort(int r[],int n) { for(int i=2;i<=n;i++) { int temp=r[i]; for(int j=i-1;temp<r[j];j--) { r[j+1]=r[j]; } r[j+1]=temp; } }
希尔排序的C++代码实现
/* * 前置条件:无顺序的一个数组 * 输 入:数组以及数组长度 * 处 理:对数组完成直接插入排序 * 输 出:有序数组 * 后置条件:无 */ void ShellSort(int r[],int n) { int temp; for(int d=n/2;d>=1;d=d/2) { for(int i=d;i<n;i++) { for(int j=i-d;j>=0&&r[j]>r[j+d];j=j-d) { temp=r[j]; r[j]=r[j+d]; r[j+d]=temp; } } } }
四、时间空间、效率、稳定性分析：
排序类型
直接插入排序（InsertSort）
希尔排序(ShellSort)
最好执行时间
O(n)
接近O(n2)
最坏执行时间
O(n2)
平均执行时间
O(n2)
额外辅存空间
1
1
稳定性
稳定
不稳定
五、实际应用；
待续
参考文献：算法导论
转载于:https://www.cnblogs.com/sunny-shiny/p/3869625.html
相关资源：各显卡算力对照表！