最近在学习算法与数据结构，算法是一个程序员的基本功，但是我不是科班出身，所以这方面的知识有所欠缺。在慕课网上找到一套对应的课程，主讲老师是liuyubobobo,从我学习的感受和体验来看，bobo老师对一个问题讲解的相当清晰和透彻，普通话说的也好，适合初学者理解和学习。大家如果想学习算法与数据结构的知识，我推荐这一套教程。地址链接：https://coding.imooc.com/class/71.html。 这一系列文章主要是对这套课程的内容以文字的形式展示。做这个事情一是想对视频上的知识点在通过形成文字的过程中，加深自己的理解。二是想加强自己的表达能力。
这篇文章主要讲解3个基础的排序算法，选择排序，插入排序，以及冒泡排序，其时间复杂度都是0(n^2)级别的，实现代码使用c++语言。
选择排序
首先给定一个元素是无序的整数数组：
需要对这个数组中的8个整数进行从小到大的排序。
选择排序的基本思路
首先从起始位置index = 0开始，遍历一遍数组，获取到最小的元素值index = 4 的元素，元素值为1，然后将index = 0与index = 4 上的两个元素交换位置，此时index = 0 上的元素值1。index = 4上的元素值为5。红色为已排序完成的有序区域。
找到了最小的元素放在数组的第一位后，接着从index = 1开始往后遍历数组。找到第二小的元素后再与index = 1的位置交换元素，此时，index = 1上的元素值为2，index = 2 上的元素为4.
接着再从index = 2的位置往后遍历数组，找到第三小的元素后再与index = 2上的元素交换位置，交换后，index = 2上的元素为3，index = 5 上的元素为4。
然后依此遍历的方法，直到数组的最后一个位置存放的是最大的元素。选择排序的整体思想不难理解，就是循环一遍数组找到循环元素中最小的元素，再与已排好序的下一个索引上的元素交换位置。
代码实现
我写成一个函数，传入一个数组以及元素的个数：
template <typename T>
void selectionSort(T arr[],int n){
for (int i = 0; i < n; i++) {
int minIndex = i; // minIndex保存内层循环中最小值的索引
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
插入排序
插入排序的基本思路
bobo老师打个这样一个比方，我觉得用来理解插入排序非常合适：就好像有一副牌，三个人用这副牌来斗地主，分牌阶段，你需要将你摸到的牌放在手中的牌中的合适位置，手中的牌是整理好的，是有序的，放入后，使其整体依旧有序。我们来模拟一下这个过程。首先固定手中有一张牌，用红色标记为手中已整理好的牌。
接着摸第二张牌，为4，比5小，所以放在5的前面，4与5交换位置。
接着摸第三张牌，为2，2比5小，所以先放在5的前面，4的后面。
此时这里并不是2合适的位置，继续和前面的元素比较，2比4小，所以要放到4的前面。此时变成有序了。
[图片上传失败...(image-231474-1535017882614)]
接着再摸第四张牌，为7，7比5小，发现不用交换位置，放在原地就好了。
就这样，按照这个方法，将摸到的牌与整理好的牌依次做比较，使其放在合适的位置，直到摸完最后一张牌。
代码实现
template <typename T>
void insertionSort(T arr[],int n){
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (arr[j-1] > arr[j]) {
swap(arr[j - 1],arr[j]);
} else {
break;
}
}
}
}
注意：第一层for循环时 i = 1，i不是从零开始。因为第一张牌不需要排序，从第二张牌开始。所以设置i = 1。
在[0 i) 前闭后开这个区间中为已排好序的元素，i为待排序的元素的索引，第二层for循环是从待整理的元素索引i开始。在已排好序的区间[0,i)中，从后往前遍历。 如果发现前面的元素比它大，则两个元素交换位置。当发现前面的元素比它小的时候，此时它就找到了合适的位置。就不需要再遍历了，直接结束这一层循环。
插入排序优化
在交换两个元素位置的时候,调用了swap(arr[j - 1],arr[j])，而一次交换其实是三次赋值，这句代码其实也可以改写为：
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
如果一个较小的元素要插入到合适的位置，肯定要一路交换很多次。这无形中就增加了排序时间。优化思路就是只进行赋值操作而不进行交换操作，先保存一份待排序的元素，然后遍历已排好序的元素，从后往前进行逐一比较，如果当遍历到index = j的元素时，j - 1索引上的元素要比j位置上的元素大，则将j - 1索引位置的元素往后挪，往后挪也就是将j索引位置的元素赋值为j-1索引位置的元素，当遍历到j-1索引上的元素比元素j位置上的元素小或相等时，就说明上一次循环往后挪而腾出来的位置为待排序的合适位置，在将该位置的值赋值为待排序的值就好了。
假定现在按照优化的思路对1进行排序，红色为已排好序的部分。
首先先复制一份待排序的元素1
然后将待排序的元素与已排好序的index = 3位置，值为7的元素比较，如果这个元素比待排序的元素要大，则直接将待排序的值复制为这个元素。7 比 1 大，7往后挪，所以待排序位置上的元素值赋值为7，而index = 3位置就腾出来了。
然后依次往前与带排序的元素比较。这次是index = 2 时的 5 与 1比较， 5比1大，5往后挪，将index = 3 位置上的元素赋值为5，index = 2这个位置就腾出来了。
再将index = 1 时的4 与 待排序的元素1比较，4 还是比1 大，4往后挪，将 index = 2位置赋值为4，index = 1这个位置就腾出来了。
继续。再将index = 0时的2, 与待排序的元素1比较，2还是比1大，2往后挪，将index = 1位置赋值为2，index = 0这个位置腾出来了。
那么腾出来的位置上为元素的前面已没有元素可以比较了。所以此时在index = 0的位置上放置上待排序的元素。
元素1经过一番波折，尘埃落定，终于找到了他合适的位置，元素1排序完毕
然后index = 5上的元素3按照上述方法找到合适的位置，index = 6 上的元素按照上述方法找到合适的位置，接着是index = 7上的元素。将所有的元素都按照上述方法找到自己合适的位置。
代码实现
template <typename T>
void insertionSort(T arr[],int n){
for (int i = 1; i < n; i++) {
T e = arr[i]; // 保存待插入索引为i时的元素e
int j = i; // j保存元素e应该插入的位置
for (j = i; j > 0; j--) {
if (arr[j-1] > e) {
arr[j] = arr[j-1];
}
}
arr[j] = e;
}
}
冒泡排序
冒泡排序实现思路
首先还是这一个由8个数组成的一个无序的数组
冒泡排序的核心思想就是将相邻的两个元素两两比较，根据大小来交换元素的位置
首先，5与4比较，5比4大，我们的需求是从小到达排列，4需要在5的前面，所以4与5交换位置，红色表示两个要交换位置的元素。
交换后
然后, 5与2开始比较，5比2大，交换位置
交换后
继续， 5和7比较，5比7小，位置保持不变
go on， 7与1比较，7比1大，交换位置
交换后
不要停，7与3比较，7比3大，交换位置
交换后
继续深入， 7与8比较，7比8小，保持不变
还有最后一个，8与6比，8比6大，交换位置
交换后
这样一轮下来，元素8排到了最右侧，此时红色代表️已排好序的区域
接着按照上述方法，重新重头开始相邻元素两两遍历，前一个元素比后一个元素大则交换位置，小则保持位置不变，一路比较下来。找到第二大的元素放到元素8的左侧。
然后是
然后是
给定的一组无序的整数数组，按照排序的思路来讲，蓝色区域属于无序的区域，还需要比较，但是上面图片中蓝色部分已经是有序的了，这可以作为一个优化的方面，就是当发现代排区域中的元素已经是有序了的时候，排序完成，结束排序，下面的代码中不涉及这部分的优化。
实现代码
template <typename T>
void BubbleSort(T arr[],int n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j],arr[j+1]);
}
}
}
}
代码不难理解，双层循环，外层每一次循环确定一个最大值放在数组的右侧，内层寻找这个最大值。先进行元素比较，满足则交换。
冒泡排序的优化
刚刚在逐步比较的时候，出现了这样一种情况：蓝色的无序区域中的元素已经是有序的了。
但是上面的冒泡排序的代码还会继续的比较下去。每一个元素都会参与外层循环，直到循环结束。所以优化方向是在无序区域中的元素已经有序了的情况下结束循环。
优化后的代码,部分解释见注释。
void BubbleSort(T arr[],int n){
for (int i = 0; i < n; i++) {
bool isSorted = true; // 用一个bool值来标记每一层是否是有序的，默认为true.
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j],arr[j+1]);
isSorted = false; // 如果有交换元素，那么不是有序，该bool值改为false.
}
}
if (isSorted) { // 在内层中，如果该bool值没有被改为false,那么就说明内层没有元素交换，那么该数列排序完成了，直接结束循环。
break;
}
}
}
这个优化主要是用一个bool值做标记，来确定是否有序。在内层循环中如果没有元素交换，那么这个数列肯定就是有序的了，那么外层就无需在循环了。
下次学习内容：归并排序
