什么是网站的域名,公司官网模板,百度企业网站建设费用,网站制作厂家文章目录 #x1f680;前言#x1f680;冒泡排序✈️冒泡排序的逻辑✈️冒泡排序coding #x1f680;选择排序✈️选择排序的逻辑✈️选择排序coding #x1f680;前言
这里是阿辉算法与数据结构专栏的第一篇文章#xff0c;咱们就从排序算法开始讲起#xff0c;排序算法… 文章目录 前言冒泡排序✈️冒泡排序的逻辑✈️冒泡排序coding 选择排序✈️选择排序的逻辑✈️选择排序coding 前言
这里是阿辉算法与数据结构专栏的第一篇文章咱们就从排序算法开始讲起排序算法有很多大致分为两类基于比较的排序和非比较的排序
基于比较的排序冒泡、选择、插入、希尔、堆、归并、随机快排非比较的排序桶排序
以上的排序算法阿辉都会讲到今天阿辉主要讲一下选择排序和冒泡排序。 铁子们进入咱们今天的学习吧!
冒泡排序
铁子们对于冒泡排序一定是有很多理解了这里阿辉就简单讲一下
✈️冒泡排序的逻辑
逻辑很简单就是前一个数据与后一个数据进行比较前一个数据更大就交换相等或小于不进行任何操作然后重复操作一趟下来就能把最大的数据放到末尾位置然后重复上述操作如下图 可以看出对于上面具有5个元素的无序数组我们通过4趟的冒泡后就将其变为有序数组每一趟冒泡后都可以使剩下的数据中最大的数据沉底 我们看一下动图演示
✈️冒泡排序coding
其实很多情况下我们对于逻辑掌握的很快关键是把逻辑抽象成代码的过程很麻烦各种边界要考虑到位对于一个算法首先要把具体例子搞明白再去写否则很容易脑子一摊浆糊
关于冒泡排序其实我们就关注两件事
1.需要几趟冒泡
对于一个有n个元素的数组我们需要 n-1 趟冒泡
很好理解比如3 2 1这三个数
一趟冒泡会把3移到末尾变成 2 1 3
第二趟就会把2移到3的前一位变成 1 2 3这时数组已经有序了
2.一趟冒泡进行几次比较
对于有n个元素的数组来说
第一次冒泡范围是下标0 ~ n-1就比较n-1次
第二次冒泡范围是下标0 ~ n-2就比较n-2次
第三次冒泡范围是下标0 ~ n-3就比较n-3次… … … …有了上面的分析我们很容易想到可以用一个循环控制趟数再用一个循环控制比较的次数就可以写出下面经典的冒泡排序
//交换方法
void swap(int a[], int x, int y)
{int tmp a[x];a[x] a[y];a[y] tmp;
}
//经典冒泡排序
void BubbleSort(int a[], int sz)//sz表示传入数组的大小
{//end表示需要进行几趟冒泡for (int end sz - 1; end 0;end--){//同时end从sz-1开始作为比较次数限定第二个for循环的范围//每一趟冒泡都是从下标 0和1 1和2 2和3 ……比较//second代表每次比较的第二个数也就是0和1的1,1和2的2//所以second从1开始for (int second 1; second end; second){//当第一个数大于第二个数就交换if (a[second - 1] a[second]){//交换函数传入数组名和需要交换的两个数的下标swap(a, second, second - 1);}}}
}为什么说上述是经典的冒泡排序因为他有一个缺陷对于长度一样的数组不管其是否有序都会进行固定次数的比较这样的话效率很差所以就有冒泡排序的改良版
void BubbleSort(int a[], int sz)
{for (int end sz - 1; end 0;end--){int flag 0;//增加一个flag变量判断是否数组已有序for (int second 1; second end; second){if (a[second - 1] a[second]){swap(a, second, second - 1);flag 1;}}//flag为0说明没进行交换没交换就说明每个数的前一个数不大于它//说明数组已有序跳出循环if (flag 0)break;}
}选择排序
选择排序也不难阿辉来给铁子们稍微讲一下
✈️选择排序的逻辑
逻辑就是对于一个有n个元素的数组首先在下标为0 ~ n-1的范围内找到最小的数与下标为0的数交换染后在下标1 ~ n-1范围找到最小的数与下标为1的数字交换然后按照上述依次进行直到排好序 选择过程
我们来看一下动图展示
✈️选择排序coding
同样选择排序我们也只关心两件事
1.进行几次找最小值
这与冒泡类似一个有n个元素的数组进行n-1次选择
2.每次寻找最小值的范围
对于有n个元素的数组来说
对于有n个元素的数组来说
第一次选择范围是下标0 ~ n-1
第二次选择范围是下标1 ~ n-1
第三次选择范围是下标2 ~ n-1
…………有了上面的分析我们很容易想到可以用一个循环控制找最小值的次数再用一个循环遍历要找的最小值的范围
//交换方法
void swap(int a[], int x, int y)
{int tmp a[x];a[x] a[y];a[y] tmp;
}
//选择排序
void SelectSort(int a[],int sz)//sz数组元素个数
{int first 0;//控制找最小值并且是每一次要找最小值的范围的第一个元素的下标for (first 0; first sz - 1; first){int end sz - 1;//控制遍历最小值的范围并且从后遍历数组int min first;//min记录最小值的下标while(end first){//如果以end为下标的元素比以min为下标的元素小min就记录该数的下标min a[min] a[end] ? end : min;end--;}swap(a, first, min);//每次找到的最小数与开始位置交换}
}以上GIF动图均出自这篇文章 如果觉得文章对你有帮助的话还请点赞关注收藏支持博主如有不足还请指点博主及时改正感谢大家支持
