在我们内存中我们一般会有一些没有顺序的数据，我们成为内排序，而今天分享八大排序的是时间复杂度为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）的排序也是终于完成了。我们下次来讲讲在插入排序的基础上实现希尔排序。