【排序算法】C语言实现选择排序与冒泡排序

简介: 【排序算法】C语言实现选择排序与冒泡排序

🚀前言

这里是阿辉算法与数据结构专栏的第一篇文章,咱们就从排序算法开始讲起,排序算法有很多大致分为两类:基于比较的排序和非比较的排序

  • 基于比较的排序:冒泡、选择、插入、希尔、堆、归并、随机快排
  • 非比较的排序:桶排序

以上的排序算法阿辉都会讲到,今天阿辉主要讲一下选择排序和冒泡排序。

铁子们,进入咱们今天的学习吧!!!

🚀冒泡排序

铁子们对于冒泡排序一定是有很多理解了,这里阿辉就简单讲一下😆

✈️冒泡排序的逻辑

逻辑很简单,就是前一个数据与后一个数据进行比较,前一个数据更大就交换,相等或小于不进行任何操作,然后重复操作,一趟下来就能把最大的数据放到末尾位置然后重复上述操作如下图👇

可以看出,对于上面具有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动图均出自这篇文章

如果觉得文章对你有帮助的话,还请点赞,关注,收藏支持博主,如有不足还请指点,博主及时改正,感谢大家支持!!!

相关文章
|
15天前
|
机器学习/深度学习 搜索推荐 算法
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
|
1天前
|
搜索推荐
排序算法---冒泡排序----详解&&代码
排序算法---冒泡排序----详解&&代码
|
1天前
|
搜索推荐
排序算法---选择排序-----详解&&代码
排序算法---选择排序-----详解&&代码
|
3天前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用,包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现,通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数,分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例,展示了递归的优雅与效率。然而,递归可能导致栈溢出,需注意优化。学习递归深化了对“分而治之”策略的理解。**
14 7
|
7天前
|
算法 搜索推荐
数据结构与算法-选择排序
数据结构与算法-选择排序
9 4
|
7天前
|
算法 搜索推荐
数据结构与算法-冒泡排序
数据结构与算法-冒泡排序
9 2
|
11天前
|
算法 搜索推荐 Java
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
9 0
|
12天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
10 0
|
12天前
|
存储 算法 C语言
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
9 0
|
12天前
|
人工智能 算法 C语言
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
10 0