以插入算法的实现为例，从一开始写下思路，到证明循环不变式，从完全在主函数中书写，到把某些步骤写成函数，再到把这一算法写成类，而后分析时间复杂度
目录
算法的实现
思路（循环不变式）
- 假定我们有一个已经按照从小到大排好序的n个数字，再增加一个数字，如何将这n+1个数字排序？显然只需要把这新增的数字放到它该在的位置上，而其他的数字相对位置不变，这样就排好序了。对这个第n+1个数字而言，如果它比原来n个数字中最后一个数字也就是最大的那个数字大，那么它的位置就是在最后面。如果不是，那么可以知道这个数字的位置绝不是最后面，后续也不用在和第n个数字比较。这时候它需要和第n-1个数字比较...重复上述过程，最终找到一个数字比它小，那么它的位置也就确定了，这样就实现了n+1个数字的排序
- 而实际上我们面对的是n个毫无顺序的数字，但即使如此，对于第一个数字而言，这个数字本身是排好序的，第二个数字之于第一个数字相当于增加的那一个数字，按上述完成排序后，第三个数字之于前两个数字又相当于增加的那一个数字...最终第n个数字之于前n-1个数字相当于增加的数字，经比较即可完成排序
- 举个例子：2，5，4，9，3，第一次是5和2比较，保持不变，前两个数字完成排序，第二次是4和（5，2）比较，4和5交换位置，变为（2，4，5，9，3），第三次9和（2，4，5）比较，位置不变，第四次是3和（2，4，5，9）比较，9和3交换位置，5和3交换位置，4和3交换位置，变为（2，3，4，5，9），排序完成
- 这种都是每次将“新增的数字”“插入”原来n个已经排好序的数字，这就是循环不变式，下面给出定义：1、初始：保证在初始的时候不变式为真。
2、保持：保证在每次循环开始和结束的时候不变式都为真。
3、终止：如果程序可以在某种条件下终止，那么在终止的时候，就可以得到自己想要的正确结果。
在这三个部分中，前两个是条件，最有一个是结论。（具体可参考本站博主的文章）https://blog.csdn.net/weixin_33720956/article/details/91790171?fromshare=blogdetail&sharetype=blogdetail&sharerId=91790171&sharerefer=PC&sharesource=ftgchtcju&sharefrom=from_link - 下面给出本算法的证明： 1.在刚开始，只有第一个数字，而这个数字显然是有序的 2.第一个数字有序到前两个数字有序，再到第三个数字有序...所以当k个数字有序，“插入”第 k+1个数字时也是有序的，当这k+1个数字排好序后也是有序的 3.程序终止时，也就是将第n个数字“插入”到n-1个已经排好序的数字中，结束时所有数字都是 有序的，证明完毕
做法
完全在主函数中书写（实现一）
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;//获取需要创建的数组空间大小
int* p = new int[n];//创建数组空间
for (int i = 0; i < n; i++) {
cin >> *(p + i);//逐个获取数字
}
for (int i = 1; i < n; i++) {
int j = 0;//实现排序，从前往后进行，从后往前比较
while (*(p + i - j) < *(p + i - 1 - j) && (i - j - 1 >= 0)) {
int t = *(p + i - j);
*(p + i - j) = *(p + i - 1 - j);
*(p + i - 1 - j) = t;
j++;
}
}
for (int i = 0; i < n; i++) {
cout << *(p + i) << " ";
}
}
先在控制台确定要输入几个数字，创建有相应空间的数组，再逐个输入数字，该过程完全在主函数中书写
注意
while (*(p + i - j) < *(p + i - 1 - j) && (i - j - 1 >= 0)) {
int t = *(p + i - j);
*(p + i - j) = *(p + i - 1 - j);
*(p + i - 1 - j) = t;
j++;
}中间这一步骤，是在后面数字比前面数字小的情况下，将这两个数字进行交换，其中交换的过程可以写成函数
将“交换”写成函数
//交换函数
void exchange(int &a, int &b) {
int t = a;
a = b;
b = t;
}这样这一步就可以变成
while (*(p + i - j) < *(p + i - 1 - j) && (i - j - 1 >= 0)) {
exchange(*(p + i-j), *(p + i - 1 - j));//调用交换函数
j++;
}交换这一步骤可以写成函数，那么同样地，实现这一排序本身自然也是可以写成函数的
将“排序”写成函数
void insert(int* p, int n) {//将原代码写成函数
for (int i = 1; i < n; i++) {
int j = 0;
while (*(p + i - j) < *(p + i - 1 - j) && (i - j - 1 >= 0)) {
exchange(*(p + i-j), *(p + i - 1 - j));
j++;
}
}
}
于是在主函数中就简化成了
int main()
{
int n;
cin >> n;
int* p = new int[n];
for (int i = 0; i < n; i++) {
cin >> *(p + i);
}
insert(p, n);//调用函数
for (int i = 0; i < n; i++) {
cout << *(p + i) << " ";
}
}如果再把其他步骤也写到函数里，对insert函数改造一下
将几乎所有步骤都写成函数
template<typename T>
void insert(T* p, int n) {
for (int i = 0; i < n; i++) {
cin >> *(p + i);
}
for (int i = 1; i < n; i++) {
int j = 0;
while (*(p + i - j) < *(p + i - 1 - j) && (i - j - 1 >= 0)) {
exchange(*(p + i-j), *(p + i - 1 - j));
j++;
}
}
for (int i = 0; i < n; i++) {
cout << *(p + i) << " ";
}
}这里还用上了一个小小的分支知识点——模板，用了模板后，这个指针的类型就不会卡死，增加其泛用空间
那在主函数里就剩下了
（实现二）
int main()
{
int n;
cin >> n;
int* p = new int[n];
insert(p, n);
}这样极其简洁（但实际上一个函数里不应该同时实现如此多的功能），只需要在关键步骤加上注释即可
而既然都简化为函数了，那么自然就能进一步写成类，调用的时候也会更方便
将这一过程写成类
class Insert//含义为“插入排序类”
{
public:
friend void exchange(int& a, int& b);
void get_arr();
void insert();
void show_arr();
private:
int _n;
int* _p;
};
在该类中，它的数据只有空间大小以及一个数组指针，指向一个动态空间，设为private，函数则有负责获取的，实现排序的以及输出在控制台的，由于交换函数并非独属于该类中的功能，在他处书写并在此设为友元函数
各函数的定义
void Insert::get_arr()//获取数组空间的大小，创建动态空间并逐个输入数字
{
cin >> _n;
_p = new int[_n];
for (int i = 0; i < _n; i++) {
cin >> *(_p + i);
}
}
void Insert::insert() //排序的实现
{
for (int i = 1; i < _n; i++) {
int j = 0;
while (*(_p + i - j) < *(_p + i - 1 - j) && (i - j - 1 >= 0)) {
exchange(*(_p + i - j), *(_p + i - 1 - j));//类外的交换函数，在此处使用实际上并不需要设为友元函数
j++;
}
}
}
void Insert::show_arr() //负责将排好序的各数字逐个输出
{
for (int i = 0; i < _n; i++) {
cout << *(_p + i) << " ";
}
}
之后在主函数中，则只需写成
（实现三）
int main()
{
Insert ser;//定义
ser.get_arr();//获取
ser.insert();//排序
ser.show_arr();//输出
}对这一个算法而言，可能写成类是大材小用，但实际上，排序有多种方法，将来完全可以写一个“排序类”用于保存所有实现排序的算法，想用哪个直接调用类中的成员即可，相当方便
分析算法（时间复杂度）
分析算法的结果意味着预测算法需要的资源。虽然有时我们主要关心像内存,通信带宽或计算机硬件这类资源，但是通常我们想度量的是计算时间。一般来说，通过分析求解某个问题的几种候选算法，我们可以选出一种最有效的算法。这种分析可能指出不止一个可行的候选算法，但是在这个过程中，我们往往可以抛弃几个较差的算法，在此就用时间复杂度来表示
考虑最佳情况，在进行排序前就已经拍好了序，那么从第二个数字开始，所有数字都只会比较一次，运行次数为n-1，所以时间复杂度为O(n）
最坏情况，各数字刚好是逆序的，那么第二个数字需要比较1次，第三个需要比较2次...第n个数字需要比较n-1次，运行次数为1+2+……+n-1，最终最高次数为2，所以时间复杂度为O（n²）
一般而言，考虑的时间复杂度是考虑最坏情况，因为更容易发生，这种情况下再用插入排序就不是很合适了，时间会增长的很快，就该考虑别的算法了
小结
在这一学期，学习了io函数，头文件，后来将一些步骤写成函数，再后来用上了指针，使用了数组，也学习了类与对象，本文是对以上所有以插入算法来实现简要概括
标签：数字,int,插入排序,++,不变式,算法,循环,排序,函数 From： https://blog.csdn.net/ftgchtcju/article/details/144700001