冒泡排序与选择排序详解

2023-06-19 46

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 冒泡排序与选择排序详解

冒泡排序与选择排序

算法步骤

以从小到大排序为例：

比较相邻元素，如果前面的比后面的元素大，则两元素交换位置

对每一对相邻元素进行比较，大的放后，这样最后的元素将是最大的元素

对越来越少的混乱元素重复上述步骤（最后的元素已经有序，不需比较），直到没有元素需要交换位置

动图演示

实现代码

#include<stdio.h>
int main()
{
  int a[]={12,134,46,688,563,145,7357,26,24};
  int i,j,flag,temp;
  for(i=0;i<sizeof(a)/sizeof(int)-1;i++)      //循环总次数为元素数量-1
  {
    flag=1;         //设置标记
    for(j=0;j<sizeof(a)/sizeof(int)-i-1;j++)  //从第一对元素开始，对每对元素进行比较，一共比较元素数量-1-i次（最后i个元素已经有序）
      if(a[j]>a[j+1])
      {
        temp=a[j];
        a[j]=a[j+1];
        a[j+1]=temp;
        flag=0;       //若有元素交换则使标记值为0
      }
    if(flag)      //若标记值未改变，则说明未发生元素交换，说明元素已经有序，退出排序
      break;
  }
  for(i=0;i<sizeof(a)/sizeof(int);i++)    //打印有序数组
    printf("%-5d",a[i]);
  return 0;
}

选择排序

算法步骤

以从小到大排序为例：

方法一：直接交换数组元素

将第一个元素与其他元素进行比较，若其他元素小于第一个元素，则交换位置，最后第一个元素为最小元素

将剩余元素的第一个元素与其他元素进行比较，若其他元素小于第一个元素，则交换位置

重复上述步骤，直到第（n-1）个元素比较完毕

方法二：利用数组下标间接交换数组元素

将第一个元素的下标标记为min，将第一个元素与其他元素进行比较，若其他元素小于第一个元素，则令该元素的数组下标为min，一轮比较完后，若第一个元素的下标不等于min，则交换第一个元素与下标为min的元素的位置

对剩下的元素重复上述步骤，直到没有元素需要交换位置

动图演示

实现代码

#include<stdio.h>
void WayOne(int *p,int num)   //利用直接交换数组元素，从小到大排列数组
{
  int i,j,temp;
  for(i=0;i<num-1;i++)    //需比较（数组元素-1）次
    for(j=i+1;j<num;j++)
      if(p[i]>p[j])
      {
        temp=p[i];
        p[i]=p[j];
        p[j]=temp;
      }
  for(i=0;i<num;i++)
    printf("%-5d",p[i]);
}
void WayTwo(int *p,int num)   //利用元素下标间接交换数组元素，从大到小排列数组
{
  int i,j,temp,max;
  for(i=0;i<num-1;i++)
  {
    max=i;      //设置标记
    for(j=i+1;j<num;j++)
      if(p[j]>p[max])
        max=j;
    if(max!=i)
    {
      temp=p[max];
      p[max]=p[i];
      p[i]=temp;
    }
  }
  for(i=0;i<num;i++)
    printf("%-5d",p[i]);
}
int main()
{
  int a[]={12,134,46,688,563,145,7357,26,24};
  WayOne(a,sizeof(a)/sizeof(int));
  printf("\n");
  WayTwo(a,sizeof(a)/sizeof(int));
  return 0;
}