在我们内存中我们一般会有一些没有顺序的数据，我们成为内排序，而今天分享八大排序的是时间复杂度为O（N^2）的插入排序，选择排序和教学意义比较强的冒泡排序。
插入排序
这是插入排序的动图，通过动图我们也是可以看到我们的插入排序的思想
从当前的位置往前找小，如果当前位置的值是比前面的位置下的，前面位置往后挪动覆盖，因为会覆盖当前的位置，所以我们需要一个key来保存我们的当前的位置，如果往前找位置的时候，这个位置的值是比我们当前位置的值小的时候，循环就开始停下来，这个时候我们退出循环，在进行插入就是插入排序，我们先来看看我们的代码，然后画图来给大家看看。
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int key = a[end + 1];
while (end >= 0)
{
if (a[end] > key)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = key;
}
}代码是很简短的，我们给个数组是{9， 8， 7， 6， 5， 4， 3， 2， 1}。
end需要往前移动找小，如果比他大，那这个位置的数就得往后移动。
选择排序
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
int mini = j;
for (int i = j; i < n; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
i++;
}
Swap(&a[mini], &a[j]);
}
}这个就是选择排序的基础玩法，但是这个选择排序我们一次只找出最小的值，我们这里还是遍历一遍数组了，遍历一遍数组只找出一个值还是有点亏，所以我们可以优化一下，一次性找出两个值，分别是最大值和最小的值，但是！优化后还是有些缺点，就是存在覆盖问题，我们来先看看代码吧。
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
优化之后判断哪个地方需要我们注意一下，因为begin的位置可能开始就是最大值，这里还需要注意的就是我们的maxi和mini一定要放到循环里面，因为你不放进去他每次都是从一开始的begin，就是下标0开始，这样会打乱我们刚开始的排序。
冒泡排序
冒泡排序还不简单，我们直接手搓，要是这个小编还能写错，我直接eat big shit
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int j = 0;
for (j = 0; j < n -1 - i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}那我们的三个时间复杂度是O（N^2）的排序也是终于完成了。我们下次来讲讲在插入排序的基础上实现希尔排序。