排序分类
插入排序：直接插入排序，希尔排序
选择排序：选择排序，堆排序
交换排序：冒泡排序，快速排序
归并排序
插入排序
直接插入排序
相当于摸牌，例如我们现在手上有{2，4，5，6}这些牌，当下一张是3的时候我们要将3插入到2和4当中，那么对于数组我们就要 把4，5，6 都往后挪，给3让出一个位置，这里演示以下往后挪的过程。
现有2，4，5，6
3先和6比，3应该放在6的前面，也就是3和6交换，交换后2，4，5，3，6
3再和5比，3应该放在5的前面，也就是3和5交换，交换后2，4，3，5，6
3再和4比，3应该放在4的前面，也就是3和4交换，交换后2，3，4，5，6
3再和2比，3应该放在2的后面，3本来就在2的后面，那就不用交换了，这就结束了
很明显，这个要用到循环，既然用到，那么就要有结束条件--------插入的数大于前一个数。
这个是一个，模拟的过程，但我们一般情况下遇到的都是一个固定长度的数组，也就是说，在不动空间的条件下只是比较交换。
假设现在是这样的一个数组{ 2,3,1,4,2,5,2,0}我们可以先从第一2位置开始排，接着就是3，1，4...把他们放到该放的位置
先排2，结果如下
第一趟：2，3，1，4，2，5，2，0
在排3，和他前面的2进行比较，不用交换，结果如下：
第二趟：2，3，1，4，2，5，2，0
在排1，和前面的3进行比较，需要交换结果如下：
2，1，3，4，2，5，2，0
还没有到达循环结束条件（插入的数大于前一个数）所以需要继续和前面的二进行比较，进行交换，结果如下：
1，2，3，4，2，5，2，0，交换后也没有到达循环结束条件，但是1的前面已经没有数了，这样也是结束了1的排序，所以上面的循环结束条件应该在加一个插入的数下标已经为0；因此第三趟排序结果为：
第三趟：1，2，3，4，2，5，2，0
剩下的数依次类推...
#include<iostream>
#include<vector>
using namespace std;
void swap(int& a, int& b)
{
int tmp=a;
a = b;
b = tmp;
}
int main()
{
vector <int>arr = { 2,3,1,4,2,5,2,0};
cout << "排序前:";
for (int i = 0; i < arr.size(); i++)cout << arr[i] << ' ';
for (int i = 1; i < arr.size(); i++)//i是要排的数
{
int t = i;
for (int j = i - 1; j >=0; j--)//
{
if (arr[t] < arr[j])
{
swap(arr[t--], arr[j]);
}
else
break;
}
}
cout << endl<<"排序后:";
for (int i = 0; i < arr.size(); i++)cout << arr[i] << ' ';
return 0;
}时间复杂度分析
时间复杂度最差的时候：也就是 逆序的时候,下面是他们每次交换后的样子
#include<iostream>
#include<vector>
using namespace std;
void swap(int& a, int& b)
{
int tmp=a;
a = b;
b = tmp;
}
int main()
{
vector <int>arr = {8,7,6,5,4,3,2,1,0};
cout << "排序前:";
for (int i = 0; i < arr.size(); i++)cout << arr[i] << ' ';
cout << endl<<endl;
for (int i = 1; i < arr.size(); i++)//i是要排的数
{
int t = i;
for (int j = i - 1; j >=0; j--)//
{
if (arr[t] < arr[j])
{
swap(arr[t--], arr[j]);
for (int i = 0; i < arr.size(); i++)cout << arr[i] << ' ';
cout << endl;
}
else
break;
}
//cout <<"比较:"<<i<<"次"<<endl;
cout << endl;
}
cout << endl<<"排序后:";
for (int i = 0; i < arr.size(); i++)cout << arr[i] << ' ';
return 0;
}每次交换的次数类似一个等差数列，因此时间复杂度就是O()
时间复杂度最好的时候也就是正序的时候，每次交换后如下图所示：
#include<iostream>
#include<vector>
using namespace std;
void swap(int& a, int& b)
{
int tmp=a;
a = b;
b = tmp;
}
int main()
{
vector <int>arr = {0,1,2,3,4,5,6,7,8};
cout << "排序前:";
for (int i = 0; i < arr.size(); i++)cout << arr[i] << ' ';
cout << endl<<endl;
for (int i = 1; i < arr.size(); i++)//i是要排的数
{
int t = i;
for (int j = i - 1; j >=0; j--)//
{
if (arr[t] < arr[j])
{
swap(arr[t--], arr[j]);
for (int i = 0; i < arr.size(); i++)cout << arr[i] << ' ';
cout << endl;
}
else
break;
}
cout <<"比较:"<<i<<"次"<<endl;
//cout << endl;
}
cout << endl<<"排序后:";
for (int i = 0; i < arr.size(); i++)cout << arr[i] << ' ';
return 0;
}可以看出就算本身是有序的，也得过一遍才可以，因此时间复杂度是O(n)
