美文网首页
一文解决CSP-J考纲所有排序算法

一文解决CSP-J考纲所有排序算法

作者: bigbigli | 来源:发表于2023-04-17 15:53 被阅读0次

    哈喽,大家好,我是bigbigli。

    上个月的今天,我发布了一篇文章
    《CSP-J大纲解读》

    关于排序知识点,在算法-基础算法中提到了CSP-J中所考察的排序知识点,有选择排序冒泡排序插入排序计数排序

    今天我们用一篇文章来复习CSP-J中所有排序知识,这里假设共n个元素,所有元素是从小到大排列。

    选择排序

    从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置

    然后再从剩余的未排序元素中寻找到最小元素,然后放到已排序的序列的后面

    以此类推,直到全部待排序的数据元素的个数为零。

    void Selection(int a[],int n){ 
    //a为存放元素的数组,n为有多少个元素
      for(int i=1;i<n;i++){
      //外层循环是当前数组空间的元素a[i],它要与后面所有的元素比较大小,最后一个数不需要再比较
        for(int j=i+1;j<=n;j++){
        //a[j]需要从i的后面一个数开始,一直需要与a[i]相比较
        //一直比较到最后一个数a[j],保证a[i]经过比较后是最小的数
          if(a[i]>a[j]) swap(a[i],a[j]);
          //如果发现后面的数小,就将其移到下标为i的空间,保证a[i]是最小的数
        }
      }
    }
    

    冒泡排序

    小的元素会经由交换慢慢“浮”到顶端,就像泡泡一样,故名“冒泡排序”。

    它的工作原理是,重复地走访过要排序的元素,依次比较两个相邻的两个元素,如果前面的数比后面的数大就把他们交换过来。

    走访元素的工作重复地进行,直到没有相邻元素需要交换。

    void Bubblen(int a[],int n){ 
      for(int i=1;i<n;i++){
      //外层循环每循环一次,都能找到一个当前最大的数放到顶端(末尾)
        for(int j=1;j<=n-i;j++){
        //每两个相邻的数比较,比较完一轮,找到最大值,下次就少比较一轮(j-i)
          if(a[j]>a[j+1]){
          //相邻的两个数比较,小的放在前面
            swap(a[j],a[j+1]);
          }
        }
      }
    }
    

    插入排序

    插入排序的工作方式像许多人排序一手扑克牌。

    开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。

    为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较,当找到一个比他小的牌,就将这张牌插到它的前面。

    void Insertion(int a[],int n){
      for(int i=2;i<=n;i++){
      //假设第一张牌已经是有序的,从第二张开始插入
        int j=i-1,key=a[i];
        //新的牌(key)要与之前所有的牌比较,直到比到第一张(j=1)
        while(j>=1&&key<a[j]){
        //如果新的牌(key)小于前面的牌,那么就一直循环
          a[j+1] = a[j];//将大于key的牌往后移
          j--;//当前下标往前移(j--)
        }
      }
    }
    

    计数排序

    给定这n个数一个有限范围(这里假设范围为1~10000),开一个不小于10000的数组,将其中所有元素初始化为0。

    假设这n个数中有个数为k,则将数组下标为k的值增加1。

    也就是说,当我们输入一个数,就将对应的数组下标的空间元素增加1。

    int a[10010]; //初始化数组所有元素
    void counting(int a[],int n){
      int k;
      for(int i=1;i<=n;i++){
        cin >> k;//每次输入的数为k
        a[k]++; //将下标为k的元素增加1,表示有一个数为k
      }
      for(int i=1;i<=10000;i++){
      //因为元素的取值范围是1~10000,所有的空间都要遍历一遍,看看有没有出现这个下标
        for(int j=1;j<=a[i];j++){
        //a[i]为下标出现的次数
          cout << i << " "; //依次输出下标即为排好的有序序列
        }
      }
    }
    

    关于排序的知识就讲到这里啦,如有想要继续了解的知识可以在下方留言哦!

    相关文章

      网友评论

          本文标题:一文解决CSP-J考纲所有排序算法

          本文链接:https://www.haomeiwen.com/subject/exscjdtx.html