网站标签怎么做跳转,廊坊企业自助建站,网页设计网站模板素材,张家口远大建设集团网站在我们内存中我们一般会有一些没有顺序的数据#xff0c;我们成为内排序#xff0c;而今天分享八大排序的是时间复杂度为O#xff08;N^2#xff09;的插入排序#xff0c;选择排序和教学意义比较强的冒泡排序。
插入排序 这是插入排序的动图#xff0c;通过动图我们也…
在我们内存中我们一般会有一些没有顺序的数据我们成为内排序而今天分享八大排序的是时间复杂度为ON^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]);}}}
}
那我们的三个时间复杂度是ON^2的排序也是终于完成了。我们下次来讲讲在插入排序的基础上实现希尔排序。
